Orientation-based models for {0,1,2}-survivable network design: theory and practice
Orientation-based models for {0,1,2}-survivable network design: theory and practice
复制标题
基于方向的 {0,1,2}-生存网络设计模型：理论与实践
DOI：
--
复制
发表时间：
2010
影响因子：
2.7
通讯作者：
Petra Mutzel
中科院分区：
文献类型：
--
作者：
Markus Chimani;Maria Kandyba;I. Ljubić;Petra Mutzel
考虑具有节点连接约束的{0,1,2-}可生存网络设计问题。在最突出的变体中，我们给出了一个边加权图和两个客户集$${\fancyscript{R}_1}$$和$${\fancyscript{R}_2}$$；我们要求一个连接所有客户的最小代价子图，并保证$${\fancyscript{R}_2}$$客户的双节点连接。我们还考虑了该问题的另一种替代方案，其中2节点连通性只需要与某个根节点及其奖品收集变体相连。本文的中心结果是通过取向性质对2节点连通图的一种新的图论刻画。这允许我们基于有向图导出两类ILP公式，一类使用多商品流，另一类使用切不等式。我们证明了这些定向模型与先前已知的ILP方法相比的理论优势。我们从多面体的角度证明了这两个概念是等价的。另一方面，我们的实验研究表明，切割配方在实践中更加强大。此外，我们还提出了一组基准实例，可用于对该主题的进一步研究。
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 $${\fancyscript{R}_1}$$ and $${\fancyscript{R}_2}$$ ; we ask for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the $${\fancyscript{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.