Spare-Capacity Assignment For Line Restoration Using a Single-Facility Type

Anantaram Balakrishnan, Thomas L. Magnanti (), Joel S. Sokol () and Yi Wang
Additional contact information
Anantaram Balakrishnan: The University of Texas at Austin, Austin, Texas 78712
Thomas L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Joel S. Sokol: Georgia Institute of Technology, Atlanta, Georgia 30332
Yi Wang: i2 Technologies Inc., Redwood City, California 94065

Operations Research, 2002, vol. 50, issue 4, 617-635

Abstract: The network restoration problem is a specialized capacitated network design problem requiring the installation of spare capacity to fully restore disrupted network flows if any edge in a telecommunications network fails. We present a new mixed-integer programming formulation for a line restoration version of the problem using a single type of capacitated facility. We examine two different models, for distinct and integrated spare-capacity systems, reflecting technologies used in synchronous transfer mode (STM) and asynchronous transfer mode (ATM) networks. The problem is NP-complete in the strong sense. We study the problem's polyhedral structure to identify strong valid inequalities that tighten the problem formulation. Our computational results on several real and randomly generated problems show that these inequalities considerably reduce the integrality gap from an average of 10% to an average of under 1%. These results indicate that strong cutting planes combined with branch-and-bound can provide efficient algorithms for solving a class of real-world problems in the telecommunications industry.

Keywords: Communications: network restoration planning. Programming; integer: capacity planning for telecommunication networks. Facilities/equipment planning; capacity expansion: installing spare capacities in communication networks (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.4.617.2853 (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:50:y:2002:i:4:p:617-635

Access Statistics for this article

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