Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem

Anantaram Balakrishnan, Thomas L. Magnanti and Prakash Mirchandani
Additional contact information
Anantaram Balakrishnan: Sloan School of Management, M. I. T., Cambridge, Massachusetts 02139
Thomas L. Magnanti: Sloan School of Management, M. I. T., Cambridge, Massachusetts 02139
Prakash Mirchandani: Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260

Management Science, 1994, vol. 40, issue 7, 846-867

Abstract: This paper studies a multi-facility network synthesis problem, called the Two-level Network Design (TLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks. We are given an undirected network containing two types of nodes---primary and secondary---and fixed costs for installing either a primary or a secondary facility on each edge. Primary nodes require higher grade interconnections than secondary nodes, using the more expensive primary facilities. The TLND problem seeks a minimum cost connected design that spans all the nodes, and connects primary nodes via edges containing primary facilities; the design can use either primary or secondary edges to connect the secondary nodes. The TLND problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we study the relationship between alternative model formulations for this problem (e.g., directed and undirected models), and analyze the worst-case performance for a composite TLND heuristic based upon solving embedded subproblems (e.g., minimum spanning tree and either Steiner tree or shortest path subproblems). When the ratio of primary to secondary costs is the same for all edges and when we solve the embedded subproblems optimally, the worst-case performance ratio of the composite TLND heuristic is 4/3. This result applies to the hierarchical network design problem with constant primary-to-secondary cost ratio since its subproblems are shortest path and minimum spanning tree problems. For more general situations, we express the TLND heuristic worst-case ratio in terms of the performance of any heuristic used to solve the embedded Steiner tree subproblem. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of a multi-level extension of this problem.

Keywords: network design; integer programming; problem formulation; valid inequalities; worst-case analysis of heuristics (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.40.7.846 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:40:y:1994:i:7:p:846-867

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().