On Stabilized Branch-and-Price for Constrained Tree Problems
On Stabilized Branch-and-Price for Constrained Tree Problems
复制标题
约束树问题的稳定分支和价格
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
G. Raidl
中科院分区：
文献类型：
--
作者：
Markus Leitner;Mario Ruthmair;G. Raidl
我们考虑一类相当通用的网络设计问题，其中一组或一个子集的给定终端节点必须连接到一个专用的根节点，通过简单的路径和各种资源和/或服务质量的限制必须得到尊重。经典Steiner树问题在图上的这些扩展可以很好地由路径公式化来建模，其中单个变量用于所有可行路径。为了在实践中解决这个公式，使用分支和价格。然而，事实证明，列生成的简单实现强烈地受到定价子问题的某些退化的影响，导致过多的运行时间。在分析了这些计算问题后，我们提出了两种方法，通过使用交替双最优解稳定列生成。这种稳定的分支和价格实际上测试的根延迟约束Steiner树问题和它的配额约束版本。结果表明，新的稳定化方法在一般情况下显着加快解决过程，远远超过分段线性稳定，我们比较。此外，我们的稳定的分支和价格表现出更好的性能比迄今领先的混合整数规划方法的基础上分层图模型和分支和切割的测试实例。由于新的稳定技术，利用替代双最优解是通用的，在这个意义上，它很容易适应于包含大量的各种进一步的约束和不同的目标函数，所提出的方法是非常有前途的一大类网络设计问题。
We consider a rather generic class of network design problems in which a set or subset of given terminal nodes must be connected to a dedicated root node by simple paths and a variety of resource and/or quality of service constraints must be respected. These extensions of the classical Steiner tree problem on a graph can be well modeled by a path formulation in which individual variables are used for all feasible paths. To solve this formulation in practice, branch-and-price is used. It turns out, however, that a naive implementation of column generation suffers strongly from certain degeneracies of the pricing subproblem, leading to excessive running times. After analyzing these computational problems, we propose two methods for stabilizing column generation by using alternative dual-optimal solutions. This stabilized branch-and-price is practically tested on the rooted delay-constrained Steiner tree problem and a quota-constrained version of it. Results indicate that the new stabilization methods in general speed up the solution process dramatically, far more than a piecewise linear stabilization to which we compare. Furthermore, our stabilized branch-and-price exhibits on most test instances a better performance than a so far leading mixed integer programming approach based on a layered graph model and branch-and-cut. As the new stabilization technique utilizing alternative dual-optimal solutions is generic in the sense that it easily adapts to the inclusion of a large variety of further constraints and different objective functions, the proposed method is highly promising for a large class of network design problems.