[Back]

M. Ruthmair, G. Raidl:
"A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems";
Talk: Conference on Integer Programming and Combinatorial Optimization (IPCO), New York, USA; 2011-06-15 - 2011-06-17; in: "Fifteenth Conference on Integer Programming and Combinatorial Optimization (IPCO XV)", (2011), 376 - 388.

We present a layered graph model for delay-constrained minimum
tree problems with a polynomial number of constraints which can
be solved well for instances with low- to medium-sized sets of achievable
delay values and not too high bounds. Layered graph models have been
recently shown to frequently yield tight bounds in the context of hopor
delay-constrained network design problems. However, since the size
of the layered graph heavily depends on the size of the set of achievable
delay values and the corresponding delay bound the practical applicability
of these models is limited. To overcome this problem we introduce an
iterative strategy in which an initially small layered graph is successively
extended in order to tighten lower and upper bounds until convergence
to the optimal solution. Computational results show the synergetic effectiveness
of both approaches outperforming existing models in nearly
all cases.

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