Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut
Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut
复制标题
具有有界环的两条边连通子图：多面体结果和分支割法
DOI：
10.1007/s10107-005-0576-5
复制
发表时间：
2006
影响因子：
2.7
通讯作者：
Pierre Pesneau
中科院分区：
文献类型：
--
作者：
B. Fortz;A. Mahjoub;S. McCormick;Pierre Pesneau
我们考虑的网络设计问题，其中包括在确定在最低成本的2边连接网络，使最短的周期（一个“环”），每个边缘属于，不超过一个给定的长度K。我们确定了一类不等式，称为循环不等式，有效的问题，并表明，这些不等式与所谓的切割不平等产生一个整数规划制定的自然设计变量的空间中的问题。然后，我们研究了与该问题相关的多面体，并进一步描述了有效的不等式类。我们给出了这些不等式是刻面定义的充要条件。我们研究了与这些不等式相关的分离问题。特别地，当K ≤4时，证明了循环不等式可以在多项式时间内分离.我们开发了一个分支和切割算法的基础上，这些结果，并提出了广泛的计算结果。
We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given lengthK. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time whenK≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.