Connectivity Upgrade Models for Survivable Network Design

Infrastructure networks to transport material, energy, and information are critical for today's interconnected economies and communities, and network disruptions and failures 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 network design decisions. This paper addresses the survivable network design problem, a core model to address the cost and redundancy tradeoffs facing network planners. Using a novel connectivity upgrading strategy, we develop several families of inequalities to strengthen a multi-commodity flow-based formulation for the problem. By raising the linear programming lower bound, these inequalities not only provide better performance guarantees for heuristic solutions but also accelerate exact solution methods and improve heuristic performance. We propose a heuristic strategy that iteratively rounds the fractional values, starting with the linear programming solution to our strong model. Extensive computational tests confirm that the valid inequalities, cutting plane algorithm, and heuristic procedure are very effective, and their performance is robust to changes in the network dimensions and desired connectivity structure. Our solution approach generates tight lower and upper bounds that are less than 0.7% apart on average