[Zurück]


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

L. Gouveia, M. Leitner, I. Ljubic:
"On the hop constrained Steiner tree problem with multiple root nodes";
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. 201 - 212.



Kurzfassung englisch:
We consider a new network design problem that generalizes
the Hop and Diameter Constrained Minimum Spanning and Steiner
Tree Problem as follows: given an edge-weighted undirected graph whose
nodes are partitioned into a set of root nodes, a set of terminals and a
set of potential Steiner nodes, find a minimum-weight subtree that spans
all the roots and terminals so that the number of hops between each relevant
node and an arbitrary root does not exceed a given hop limit H.
The set of relevant nodes may be equal to the set of terminals, or to
the union of terminals and root nodes. This paper presents theoretical
and computational comparisons of flow-based vs. path-based mixed integer
programming models for this problem. Disaggregation by roots is
used to improve the quality of lower bounds of both models. To solve
the problem to optimality, we implement branch-and-price algorithms
for all proposed formulations. Our computational results show that the
branch-and-price approaches based on path formulations outperform the
flow formulations if the hop limit is not too loose.


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


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.