Author
Listed:
- Thomas L. Magnanti
(Massachusetts Institute of Technology, Cambridge, Massachusetts)
- Prakash Mirchandani
(University of Pittsburgh, Pittsburgh, Pennsylvania)
- Rita Vachani
(GTE Laboratories Incorporated, Waltham, Massachusetts)
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.
Suggested Citation
Thomas L. Magnanti & Prakash Mirchandani & Rita Vachani, 1995.
"Modeling and Solving the Two-Facility Capacitated Network Loading Problem,"
Operations Research, INFORMS, vol. 43(1), pages 142-157, February.
Handle:
RePEc:inm:oropre:v:43:y:1995:i:1:p:142-157
DOI: 10.1287/opre.43.1.142
Download full text from publisher
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:43:y:1995:i:1:p:142-157. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.