A new partition-based heuristic for the Steiner tree problem in large graphs

Abstract

Das Steinerbaumproblem in Graphen (STP) ist ein NP-schweres kombinatorisches Optimierungsproblem, welches sowohl aus theoretischer als auch aus praktischer Sicht relevant ist. Die Anwendungsfälle reichen vom VLSI-Design bis hin zum Lösen von wissenschaftlichen Problemen in der Bioinformatik. Beim STP sollen eine Menge an Basisknoten in einem gewichteten Graphen kostenminimal verbunden werden. Da dieses Problem sehr schwierig ist, ist es nicht immer möglich eine optimale Lösung zu finden. Problematisch sind vor allem große Instanzen, die in praktischen Anwendungen relativ häufig auftreten. In solchen Fällen bleibt oft nur die Verwendung von heuristischen Methoden. Diese sind auf die Berechnung von guten, jedoch suboptimalen Lösungen in relativ kurzer Zeit spezialisiert. In dieser Diplomarbeit wird eine neue Konstruktionsheuristik vorgestellt, die Partitionierungsmethoden nutzt, um speziell mit großen Probleminstanzen umgehen zu können. Hierzu wird eine Instanz systematisch in kleinere Instanzen zerlegt, die einfach genug sind, um sie mit einem exakten Algorithmus optimal zu lösen. Danach wird eine heuristische Lösung der ursprünglichen Instanz durch Zusammensetzen der Teillösungen erzeugt. Zur Realisierung dieses Verfahrens werden sowohl exakte und heuristische Lösungsmethoden für das STP als auch Algorithmen zur Partitionierung von Graphen kombiniert. Für die Berechnung von exakten Lösungen wird ein Branch-and-Cut Verfahren verwendet. Das zugrundeliegende ILP-Model basiert auf den bekannten directed-cut-constraints, führt jedoch zusätzlich noch die Verwendung von Knotenvariablen ein. Der zugehörigen Separierungsmethode liegen verschiedene Verbesserungen aus der Literatur zugrunde. Zur Partitionierung wird das METIS Graph Partitioning Framework verwendet. Außerdem wird ein einfacher Greedy-Algorithmus vorgestellt, welcher eine Instanz durch die Kombination mehrerer Regionen in einem Voronoi-Diagram erstellt. Die implementierten Algorithmen werden zusätzlich in einen memetischen Algorithmus integriert, darunter die vorgestellte Konstruktionsheuristik, Reduktionstests, ein Algorithmus zur Rekombination von Lösungen und Variable Neighorhood Descent. Die verwendeten Nachbarschaftsstrukturen basieren auf Steiner node insertion, Steiner node elimination, key-node elimination und key-path exchange. Alle Algorithmen werden experimentell evaluiert. Die Testinstanzen dafür stammen aus der SteinLib, welche eine Sammlung von Benchmark-Instanzen für das STP darstellt, und aus einer Gruppe aus neuen Instanzen, die Netzwerkdesignprobleme aus der Praxis beschreiben. Die Ergebnisse zeigen, dass Lösungsqualität und Laufzeit des vorgestellten Verfahrens auch für große Instanzen akzeptabel sind.

The Steiner tree problem in graphs (STP) is a fundamental NP-hard combinatorial optimization problem of theoretical and practical interest. Common applications range from VLSI design to problems in computational biology. The STP can be informally described as the problem of connecting a subset of special vertices called terminals in a weighted graph at minimum cost. Due to the problem's complexity the computation of optimal solutions may not always be feasible. This holds true especially for large-scale instances which are quite common in real-world scenarios. In such cases, heuristic methods specialized on finding near-optimal solutions in reasonable amounts of time, are generally the only choice. In this master's thesis we propose a new partition-based heuristic for the efficient construction of approximate solutions to the STP in very large graphs. Our algorithm is based on a partitioning approach in which instances are divided into several subinstances which are small enough to be solved optimally. A heuristic solution of the complete instance can then be constructed through the combination of the subinstances' solutions. To this end we combine state-of-the-art exact and heuristic methods for the STP and general graph partitioning. For the exact solution of subinstances we apply a branch-and-cut procedure. The underlying integer linear programming (ILP) model augments a formulation based on the well-known directed-cut-constraints with node variables. The associated separation procedure includes several improvements from literature. For partitioning we use the METIS graph partitioning framework as well as a greedy partitioning algorithm based on the contraction of Voronoi regions. The implemented algorithms are also embedded into a memetic algorithm, which includes the partition-based construction heuristic, reduction tests, an algorithm for solution recombination and a variable neighborhood descent. We use common neighborhood structures from the STP literature: Steiner node insertion, Steiner node elimination, key-node elimination and key-path exchange. All algorithms are evaluated through practical experiments on the SteinLib, a state-of-the-art benchmark set for the STP, and a set of new real-world instances from network design. The results show that our approach yields good quality solutions with reasonable runtime, even for large graphs.