[Zurück]

M. Leitner, G. Raidl, U. Pferschy:
"Accelerating column generation for a survivable network design problem";
Vortrag: International Network Optimization Conference (INOC), Pisa; 26.04.2009 - 29.04.2009; in: "Proceedings of the International Network Optimization Conference 2009", (2009), 8 S.

We consider a network design problem occurring in the extension of ber optic networks on the
last mile which generalizes the (Price Collecting) Steiner Tree Problem by introducing redundancy
requirements on some customer nodes. In this work we present a formulation for this problem
based on exponentially many variables and solve its linear relaxation by column generation. Using
alternative dual-optimal solutions in the pricing problem we are able to signi cantly reduce the e ects
of typical e ciency issues of simplex based column generation. Computational results clearly show
the advantages of our proposed strategy with respect to the number of pricing iterations needed as
well as by means of required running times.

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