Return to results
Journal articles (2010), Mathematical Programming, 124 (1), pp. 413-440

Orientation-based models for {0,1,2}-survivable network design: theory and practice

Chimani Markus, Kandyba Maria, Ljubic Ivana , Mutzel Petra

We consider {0,1,2}-Survivable Network Design problems with node-connectivity constraints. In the most prominent variant, we are given an edge-weighted graph and two customer sets ℛ1 and ℛ2 ; we ask for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the ℛ2 customers. We also consider an alternative of this problem, in which 2-node-connectivity is only required w.r.t. a certain root node, and its prize-collecting variant. The central result of this paper is a novel graph-theoretical characterization of 2-node-connected graphs via orientation properties. This allows us to derive two classes of ILP formulations based on directed graphs, one using multi-commodity flow and one using cut-inequalities. We prove the theoretical advantages of these directed models compared to the previously known ILP approaches. We show that our two concepts are equivalent from the polyhedral point of view. On the other hand, our experimental study shows that the cut formulation is much more powerful in practice. Moreover, we propose a collection of benchmark instances that can be used for further research on this topic. Link to the article

CHIMANI, M., KANDYBA, M., LJUBIC, I. and MUTZEL, P. (2010). Orientation-based models for {0,1,2}-survivable network design: theory and practice. Mathematical Programming, 124(1), pp. 413-440.