[Back]

T. Seidl:
"A Multilevel Refinement Approach to the Rooted Delay-Constrained Steiner Tree Problem";
Supervisor: G. Raidl, M. Ruthmair; Institut für Computergraphik und Algorithmen, 2011; final examination: 2011-09.

The Rooted Delay-Constrained Steiner Tree Problem (RDCSTP) is a variant of the well-known
Steiner Tree Problem on a graph in which the paths to all terminal nodes are restricted by a
certain maximum delay. The problem mostly appears in the context of network routing for
multicasts, i.e., sending packages from a fixed source to a subset of other participants in the
network. Since the RDCSTP belongs to the class of NP-hard problems it is in general not
possible to solve large instances exactly in a reasonable amount of time. Therefore, the focus
mostly lies on developing good heuristics that can still solve large instances comparatively fast
to near optimality.
In this thesis a Multilevel Refinement heuristic - which has already been successfully applied
to other problems like the Graph Partitioning Problem - is implemented as an improvement
heuristic for the RDCSTP. In the general approach of this metaheuristic the problem´s complexity
is first iteratively reduced while still maintaining its general characteristics. The problem is
thereby simplified and can at the top level finally easily be solved. Then, the solution on this
highest level is refined until a solution for the original problem is obtained.
The algorithm introduced here implements the Multilevel Refinement approach as an improvement
heuristic, iteratively changing an existing solution. However, it is designed in a way
that also allows it to be used to construct an initial solution. Another distinctiveness is that,
due to the additional delay constraints, supplementary data structures have to be used to avoid
creating invalid solutions on higher levels as much as possible. In the refinement phase an additional
improvement algorithm, the Key Path Improvement, is executed on each level, drastically
increasing result quality.
Experimental tests are carried out, evaluating the performance of the algorithm on large instances
and comparing it to other algorithms in the literature. The obtained results are promising
and indicate that the Multilevel Refinement metaheuristic is indeed a competitive approach for
the RDCSTP.

Das Rooted Delay-Constrained Steiner Tree Problem (RDCSTP) ist eine Variante des bekannten
Steinerbaum-Problems auf einem Graphen in welcher die Pfade zu allen Zielknoten durch eine
bestimmte maximale Verzögerung beschränkt sind. Das Problem tritt hauptsächlich im Bereich
des Netzwerk-Routings beim Multicast auf, das heißt wenn Pakete von einer einzelnen Quelle
zu einer bestimmten Untermenge der anderen Netzwerk-Teilnehmer gesendet werden sollen. Da
das RDCSTP, wie das ursprüngliche Steiner-Problem, zur Klasse derNP-schwierigen Probleme
gehört, ist es allgemein nicht möglich die exakte Lösung einer großen Probleminstanz in vertretbarer
Zeit zu finden. Der Fokus der Forschung liegt daher großteils auf der Entwicklung guter
Heuristiken, die auch bei großen Probleminstanzen in der Lage sind in vergleichbar kurzer Zeit
zu möglichst guten Lösungen zu kommen.
In dieser Arbeit wird hierfür die Multilevel-Refinement-Heuristik - die bereits erfolgreich
auf etliche andere Probleme, wie das Graph Partitioning Problem, angewandt wurde - als Verbesserungsheuristik
für das RDCSTP entwickelt. Grundsätzlich werden bei dieser Metaheuristik
in einem ersten Schritt Knoten sukzessive zusammengefasst um den Graphen auf höheren "Levels",
mit weniger Knoten, darzustellen. Das so vereinfachte Problem kann dann auf der höchsten
Abstraktionsebene in simplerWeise gelöst werden. Dann wird diese Lösung schrittweise wieder
soweit verfeinert, bis eine Lösung für das ursprüngliche Problem erreicht wird.
Der hier vorgestellte Algorithmus für das RDCSTP implementiert diesen Multilevel-Ansatz
als Verbesserungsheuristik, die eine existierende Lösung iterativ verändert. Er wurde allerdings
in einer Weise entworfen, die es ihm ebenso erlaubt eine Anfangslösung selbst zu generieren.
Eine weitere Besonderheit ist, dass wegen der zusätzlichen Verzögerungs-Einschränkung weitere
Datenstrukturen benötigt werden, um auf höheren Levels möglichst gültige Lösungen zu
erzeugen. Außerdem wird während der Verfeinerung der Lösung auf jedem Level eine weitere
Verbesserungsheuristik angewandt, das Key Path Improvement, welches die Lösungsqualität
drastisch verbessert.
Umfangreiche experimentelle Tests wurden durchgeführt um die Leistungsfähigkeit des Algorithmus
bei großen Instanzen zu messen, und ihn mit anderen Algorithmen aus der Literatur
zu vergleichen. Die hierbei erhaltenen Ergebnisse sind durchwegs sehr positiv und weisen somit
darauf hin, dass der verfolgte Multilevel-Ansatz tatsächlich eine konkurrenzfähige Heuristik für
das RDCSTP darstellt.

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