A Multilevel Refinement approach to the Rooted Delay-Constrained Steiner Tree Problem

Abstract

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 auf. Da das RDCSTP zur Klasse der NP-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.<br />In dieser Arbeit wird hierfür die Multilevel-Refinement-Heuristik 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 simpler Weise gelöst werden. Dann wird diese Lösung schrittweise wieder soweit verfeinert, bis eine Lösung für das ursprüngliche Problem erreicht wird.<br />Der hier vorgestellte Algorithmus für das RDCSTP implementiert diesen Multilevel-Ansatz als Verbesserungsheuristik, die eine existierende Lösung iterativ verändert. Eine weitere Besonderheit ist, dass wegen der zusätzlichen Verzögerungs-Einschränkung weitere Datenstrukturen benötigt werden, um auf höheren Levels 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.<br />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 Ansatz tatsächlich eine konkurrenzfähige Heuristik für das RDCSTP darstellt.

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.<br />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.<br />Then, the solution on this highest level is refined until a solution for the original problem is obtained.<br />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.<br />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.<br />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.<br />