Article ID: | iaor20031686 |
Country: | United States |
Volume: | 50 |
Issue: | 4 |
Start Page Number: | 617 |
End Page Number: | 635 |
Publication Date: | Jul 2002 |
Journal: | Operations Research |
Authors: | Balakrishnan Anantaram, Magnanti Thomas L., Sokol Joel S., Wang Yi |
Keywords: | networks |
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.