Spare-capacity assignment for line restoration using a single-facility type

Spare-capacity assignment for line restoration using a single-facility type

0.00 Avg rating0 Votes
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: , , ,
Keywords: networks
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.

Reviews

Required fields are marked *. Your email address will not be published.