[Back]


Diploma and Master Theses (authored and supervised):

M. Berlakovich:
"Multilevel Heuristiken für das Rooted Delay-Constrained Minimum Spanning Tree Problem";
Supervisor: G. Raidl, M. Ruthmair; Institut für Computergraphik und Algorithmen, 2010; final examination: 2010-07.



English abstract:
Many combinatorial optimization problems are NP-hard and can not be solved exactly in an
efficient way commonly. Therefore heuristics are often applied to generate good approximations
for such problems. This thesis discusses the Rooted Delay-Constrained Minimum Spanning Tree
Problem (RDCMSTP) which is NP-hard. The task is to find a minimum spanning tree for a
given graph where the edges have cost and delay values minimizing the sum of costs. However,
an additional constraint is applied that no path from a speci ed root node to any other node
may exceed a given delay bound. An application for the given problem is a form of distribution
with a guarantee of timely delivery, for example a shipment service with a guarantee for delivery
within 24 hours.
In this document three multilevel heuristics for the RDCMSTP are introduced. A multilevel
heuristic basically consists of two steps, the coarsening and the refinement step. During the
coarsening step vertices and/or edges are systematically merged in order to create a reduced
graph. The graph is reduced in multiple iterations thus creating multiple levels of detail.
In the second step, the re nement, a solution tree is constructed using the information acquired
during the coarsening. While constructing the solution the graph can be searched for local
improvements using appropriate neighborhoods thus increasing the quality of the solution.
The results achieved by the multilevel heuristics are similar to leading existing heuristics and
there were only slight improvements. This shows, that it is possible to achieve good results for
the RDCMSTP with multilevel techniques. Additionally it is shown, that the use of multilevel
heuristics, especially for classic approaches, can be seen as an additional constraint during the
search for a solution which can have negative e ects. Especially the Component-based Multilevel
Heuristic achieves very good results and can de nitely compete with existing heuristics.

German abstract:
Viele kombinatorische Optimierungsprobleme sind NP-schwer und können deshalb höchstwahrscheinlich
nicht effizient exakt gelöst werden. Aus diesem Grund bedient man sich oft Heuristiken
um gute Näherungslösungen für derartige Probleme zu finden. In dieser Arbeit wird das Rooted
Delay-Constrained Minimum Spanning Tree Problem (RDCMSTP) behandelt. Es handelt sich
hierbei um ein NP-schweres Problem, wobei für einen gegebenen Graphen, dessen Kanten über
Kosten und einen Delaywert verfügen, ein kostenminimaler Spannbaum gesucht wird. Jedoch
besteht die Einschränkung, dass der Pfad zwischen einem beliebigen Knoten und einer de nierten
Wurzel nicht länger als eine gegebene Delaygrenze sein darf. Eine praktische Anwendung
für dieses Problem ist eine Form von Vertrieb mit einer Lieferzeitgarantie, beispielsweise ein
Paketversand mit 24 Stunden Liefergarantie.
Im Zuge dieser Arbeit werden drei Multilevel-Heuristiken für das RDCMSTP vorgestellt. Eine
Multilevel-Heuristik besteht grundsätzlich aus zwei Teilen, dem Coarsening und dem Re nement.
W ahrend des Coarsenings werden Knoten und/oder Kanten systematisch zusammengefasst
um so den Graph zu vereinfachen. Der Graph wird in mehreren Iterationen vereinfacht
und es entstehen verschiedene Ebenen des Graphen, sogenannte Levels.
Im zweiten Schritt, dem Re nement, wird, mit Hilfe der Informationen aus dem Coarsening,
sukzessiv der gesuchte Spannbaum erstellt.Während des Re nements kann der Graph, mit Hilfe
von lokalem Improvement, unter Verwendung geeigneter Nachbarschaftsstrukturen untersucht
werden, um so eine Verbesserung der Gesamtlösung zu erzielen.
Die Ergebnisse der entwickelten Multilevel-Verfahren ähneln jener führender bestehender Verfahren
bzw. werden manchmal geringfügige Verbesserungen erzielt. Dass heißt, es ist durchaus
möglich für das RDCMSTP mit Multilevel-Ansätzen gute Ergebnisse zu erzielen. Es zeigt sich
jedoch auch, dass sich die Verwendung von Multilevel-Verfahren, vor allem bei sehr klassischen
Ansätzen, als zusätzliche Einschränkungen bei der Lösungs findung negativ auswirken können.
Vor allem die Component-based Multilevel-Heuristik erzielt teilweise sehr gute Ergebnisse und
kann durchaus mit bestehenden Verfahren konkurrieren.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_188757.pdf


Created from the Publication Database of the Vienna University of Technology.