Spare-Capacity Assignment For Line Restoration Using a Single-Facility Type
Authors:
- 1 August 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 50 (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
This publication has 19 references indexed in Scilit:
- A decomposition approach to assign spare channels in self-healing networks2002
- Near optimal spare capacity planning in a mesh restorable network2002
- Telecommunication Link Restoration Planning with Multiple Facility TypesAnnals of Operations Research, 2001
- A Cutting Plane Algorithm for Multicommodity Survivable Network Design ProblemsINFORMS Journal on Computing, 1998
- Capacitated Network Design—Polyhedral Structure and ComputationINFORMS Journal on Computing, 1996
- Broadband network restorationIEEE Communications Magazine, 1996
- Distributed self‐healing network and its optimum spare‐capacity assignment algorithmElectronics and Communications in Japan (Part I: Communications), 1991
- Synthesis of a Communication NetworkJournal of the Society for Industrial and Applied Mathematics, 1964
- An Application of Generalized Linear Programming to Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1962
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961