[Zurück]

M. Leitner, M. Ruthmair, G. Raidl:
"Stabilized branch-and-price for the rooted delay-constrained Steiner tree problem";
Vortrag: International Network Optimization Conference (INOC), Hamburg, Deutschland; 13.06.2011 - 16.06.2011; in: "Network Optimization: 5th International Conference, INOC 2011", (2011), S. 124 - 138.

We consider the rooted delay-constrained Steiner tree problem which
arises for example in the design of centralized multicasting networks where quality
of service constraints are of concern. We present a mixed integer linear programming
formulation based on the concept of feasible paths which has already been
considered in the literature for the spanning tree variant. Solving its linear relaxation
by column generation has, however, been regarded as computationally not
competitive. In this work, we study various possibilities to speed-up the solution of
our model by stabilization techniques and embed the column generation procedure
in a branch-and-price approach in order to compute proven optimal solutions. Computational
results show that the best among the resulting stabilized branch-and-price
variants outperforms so-far proposed methods.

http://publik.tuwien.ac.at/files/PubDat_201612.pdf