Connectivity Upgrade Models for Survivable Network Design

Anantaram Balakrishnan (), Prakash Mirchandani () and Harihara Prasad Natarajan ()
Additional contact information
Anantaram Balakrishnan: McCombs School of Business, The University of Texas at Austin, Austin, Texas 78712
Prakash Mirchandani: Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Harihara Prasad Natarajan: School of Business Administration, University of Miami, Coral Gables, Florida 33124

Operations Research, 2009, vol. 57, issue 1, 170-186

Abstract: Disruptions in infrastructure networks to transport material, energy, and information can have serious economic, and even catastrophic, consequences. Since these networks require enormous investments, network service providers emphasize both survivability and cost effectiveness in their topological design decisions. This paper addresses the survivable network design problem, a core model incorporating the cost and redundancy trade-offs facing network planners. Using a novel connectivity upgrade strategy, we develop several families of inequalities to strengthen a multicommodity flow-based formulation for the problem, and show that some of these inequalities are facet defining. By increasing the linear programming lower bound, the valid inequalities not only lead to better performance guarantees for heuristic solutions, but also accelerate exact and approximate solution methods. We also consider a heuristic strategy that sequentially rounds the fractional values, starting with the linear programming solution to our strong model. Extensive computational tests confirm that the valid inequalities, added via a cutting plane algorithm, and the heuristic procedure are very effective, and their performance is robust to changes in the network dimensions and connectivity structure. Our solution approach generates tight lower and upper bounds with average gaps that are less than 1.2% for various problem sizes and connectivity requirements.

Keywords: integer programming; cutting plane/facet; networks/graphs; applications; theory (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0579 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:1:p:170-186

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().