[Back]


Publications in Scientific Journals:

M. Leitner, M. Ruthmair, G. Raidl:
"Stabilizing branch-and-price for constrained tree problems";
Networks, Volume 61 (2013), 2; 150 - 170.



English abstract:
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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1002/net.21484

Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_224913.pdf


Created from the Publication Database of the Vienna University of Technology.