Shared Protection Network Design: Valid Inequalities and a Decomposition Approach

Date Added: Jan 2010
Format: PDF

Shared Protection is a technique that can reduce the cost of backup resources in survivable networks, if it is suitably considered at the design level. This paper presents a model and two families of valid cut-set inequalities for this problem. Because of the computational burden brought by the problem, the authors decompose it through Lagrangian Relaxation and solve it with a bundle method strengthened by the cut-set inequalities. The authors compare the approach with an MIP solver on a set of real-world network instances, and report the difference between the cost of a network with and without applying Shared Protection.