[Zurück]

M. Ruthmair, G. Raidl:
"On Solving the Rooted Delay- and Delay-Variation-Constrained Steiner Tree Problem";
Vortrag: International Symposium on Combinatorial Optimization (ISCO), Athen, Griechenland; 17.04.2012 - 21.04.2012; in: "Proceedings of the 2nd International Symposium on Combinatorial Optimization", volume 7422 of LNCS (2012), ISBN: 978-3-642-32146-7; S. 225 - 236.

We present mixed integer programming approaches for optimally
solving a combinatorial optimization problem arising in network
design with additional quality of service constraints. The rooted
delay- and delay-variation-constrained Steiner tree problem asks for a
cost-minimal Steiner tree satisfying delay-constraints from source to
terminals and a maximal variation-bound between particular terminal
path-delays. Our MIP models are based on multi-commodity-flows and
a layered graph transformation. For the latter model we propose some
new sets of valid inequalities and an efficient separation method. Presented
experimental results indicate that our layered graph approaches
clearly outperform the flow-based model.

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