Stabilizing branch-and-price for constrained tree problems

Markus Leitner*, Mario Ruthmair, Günther R. Raidl

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


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.

Original languageEnglish
Pages (from-to)150-170
Number of pages21
Issue number2
Publication statusPublished - 1 Mar 2013
Externally publishedYes


  • branch-and-price
  • integer linear programming
  • network design
  • stabilized column generation
  • Steiner tree


Dive into the research topics of 'Stabilizing branch-and-price for constrained tree problems'. Together they form a unique fingerprint.

Cite this