Stabilizing branch‐and‐price for constrained tree problems
Stabilizing branch‐and‐price for constrained tree problems
复制标题
稳定受限树问题的分支和价格
作者：
Markus Leitner;Mario Ruthmair;G. Raidl
我们考虑一类相当通用的网络设计问题，其中给定终端节点的集合或子集必须通过简单路径连接到专用根节点，并且必须遵守各种资源和/或服务质量约束。经典斯坦纳树问题在图上的这些扩展可以通过路径公式很好地建模，其中各个变量用于所有可行路径。为了在实践中解决这个公式，使用了分支和价格。然而，事实证明，列生成的简单实现会受到定价子问题的某些退化的严重影响，从而导致运行时间过长。在分析这些计算问题后，我们提出了两种通过使用替代双最优解决方案来加速和稳定列生成的方法。由此产生的分支和价格方法在有根延迟约束斯坦纳树问题及其配额约束版本上进行了实际测试。结果表明，所提出的方法总体上显着加快了求解过程，远远超过了我们所比较的分段线性稳定。此外，我们的分支与价格方法在大多数测试实例上表现出比基于分层图的最先进的分支与剪切方法更好的性能。由于利用替代双最优解决方案的新稳定技术是通用的，因为它很容易适应包含大量的进一步约束和不同的目标函数，因此所提出的方法对于解决一大类网络设计问题非常有希望。 © 2012 Wiley periodicals, Inc. 网络，2013
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 to accelerate and stabilize column generation by using alternative dual‐optimal solutions. The resulting branch‐and‐price approach is practically tested on the rooted delay‐constrained Steiner tree problem and a quota‐constrained version of it. Results indicate that the proposed methods in general speed‐up the solution process dramatically, far more than a piecewise linear stabilization to which we compare. Furthermore, our branch‐and‐price approach exhibits on most test instances a better performance than a state‐of‐the‐art branch‐and‐cut approach based on layered graphs. 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. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013