Spare-capacity assignment for line restoration using a single-facility type
成果类型：
Article
署名作者：
Balakrishnan, A; Magnanti, TL; Sokol, JS; Wang, Y
署名单位：
University of Texas System; University of Texas Austin; Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.4.617.2853
发表日期：
2002
页码：
617-635
关键词：
摘要：
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.