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

摘要

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 R_1 and R_2; we ask for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the R_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.