This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Balakrishnan, A. Articles by Wang, Y. Search for Related Content

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

The University of Texas at Austin, Austin, Texas 78712
Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Georgia Institute of Technology, Atlanta, Georgia 30332
i2 Technologies Inc., Redwood City, California 94065
magnanti{at}mit.edu
jsokol{at}isye.gatech.edu

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.

Subject classifications: Communications: network restoration planning. Programming, integer: capacity planning for telecommunication networks. Facilities/equipment planning,capacity expansion: installing spare capacities in communication networks.
History: Received April 1998; revision received January 2001; accepted February 2001.

This article has been cited by other articles:

				A. Balakrishnan, P. Mirchandani, and H. P. Natarajan Connectivity Upgrade Models for Survivable Network Design Operations Research, January 1, 2009; 57(1): 170 - 186. [Abstract] [PDF]

				R. Bollapragada, Y. Li, and U. S. Rao Budget-Constrained, Capacitated Hub Location to Maximize Expected Demand Coverage in Fixed-Wireless Telecommunication Networks INFORMS Journal on Computing, January 1, 2006; 18(4): 422 - 432. [Abstract] [PDF]