论文标题
无法卸下流量电容网络设计的精确分离算法弧线polyhedron
An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron
论文作者
论文摘要
在本文中，我们集中精力为无法实现的电容网络设计问题生成切割平面。我们将所考虑问题的不可填充流弧线多面体用作子结构，并通过解决其上的分离问题来生成切割平面。为了减轻计算负担，我们表明，在某些特殊情况下，可以得出分离问题的封闭形式。对于一般情况，一种称为精确分离算法的蛮力算法被用于解决所考虑的多面体的分离问题，以便构造的不平等保证可以定义。此外，提出了一种新技术来加速确切的分离算法，该算法大大减少了算法中的迭代次数。最后，提出了一项关于无法估计的电容网络设计问题的全面计算研究，以证明所提出的算法的有效性。
In this paper, we concentrate on generating cutting planes for the unsplittable capacitated network design problem. We use the unsplittable flow arc-set polyhedron of the considered problem as a substructure and generate cutting planes by solving the separation problem over it. To relieve the computational burden, we show that, in some special cases, a closed form of the separation problem can be derived. For the general case, a brute-force algorithm, called exact separation algorithm, is employed in solving the separation problem of the considered polyhedron such that the constructed inequality guarantees to be facet-defining. Furthermore, a new technique is presented to accelerate the exact separation algorithm, which significantly decreases the number of iterations in the algorithm. Finally, a comprehensive computational study on the unsplittable capacitated network design problem is presented to demonstrate the effectiveness of the proposed algorithm.
