Modeling and Solving the Two-Facility Capacitated Network Loading Problem

Thomas L. Magnanti, Prakash Mirchandani and Rita Vachani
Additional contact information
Thomas L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
Prakash Mirchandani: University of Pittsburgh, Pittsburgh, Pennsylvania
Rita Vachani: GTE Laboratories Incorporated, Waltham, Massachusetts

Operations Research, 1995, vol. 43, issue 1, 142-157

Abstract: This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-to-point communication demand in a network must be met by installing (loading) capacitated facilities on the arcs: Loading a facility incurs an arc specific and facility dependent cost. This paper develops modeling and solution approaches for loading facilities to satisfy the given demand at minimum cost. We consider two approaches for solving the underlying mixed integer program: a Lagrangian relaxation strategy, and a cutting plane approach that uses three classes of valid inequalities that we identify for the problem. We show that a linear programming formulation that includes these inequalities always approximates the value of the mixed integer program at least as well as the Lagrangian relaxation bound. Our computational results on a set of prototypical telecommunication data show that including these inequalities considerably improves the gap between the integer programming formulation and its linear programming relaxation: from an average of 25% to an average of 8%. These results show that strong cutting planes can be an effective modeling and algorithmic tool for solving problems of the size that arise in the telecommunications industry.

Keywords: networks/graphs; applications: design of telecommunications networks; programming; integer; cutting plane/facet generation: facets for capacitated network design problems; programming; integer; relaxation/subgradient: comparison of Lagrangian and polyhedral approaches (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (43)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.142 (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:oropre:v:43:y:1995:i:1:p:142-157

Access Statistics for this article

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