[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

M. Leitner, M. Ruthmair, G. Raidl:
"Stabilized column generation for the rooted delay-constrained Steiner tree problem";
Vortrag: Workshop on Applied Combinatorial Optimization (ALIO/EURO), Porto, Portugal; 04.05.2011 - 06.05.2011; in: "Proceedings of the VII ALIO/EURO - Workshop on Applied Combinatorial Optimization", (2011), S. 250 - 253.



Kurzfassung englisch:
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 path based integer linear programming formulation
which has already been considered in the literature for the
spanning tree variant. Solving its linear relaxation by column
generation has so far been regarded as not competitive due to
long computational times needed. In this work, we show how to
significantly accelerate the column generation process using two
different stabilization techniques. Computational results indicate
that due to the achieved speed-up our approach outperforms so-far
proposed methods.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_201620.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.