Loading…
Thumbnail Image

Faster algorithms for Steiner tree and related problems

from theory to practice

Rehfeldt, Daniel Markus

The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. Part of its theoretical appeal might be attributed to the fact that the SPG generalizes two other classic optimization problems: Shortest paths, and minimum spanning trees. On the practical side, many applications can be modeled as SPG or closely related problems. The SPG has seen impressive theoretical advancements in the last decade. However, the state of the art in (practical) exact SPG solution, set in a series of milestone papers by Polzin and Vahdati Daneshmand, has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into the exact solution of SPGs, even the best new solvers fall far short of reaching the state of the art. This thesis seeks to once again advance exact SPG solution. Since many practical applications are not modeled as pure SPGs, but rather as closely related problems, this thesis also aims to combine SPG advancements with improvement in the exact solution of such related problems. Initially, we establish a broad theoretical basis to guide the subsequent algorithmic developments. In this way, we provide various new theoretical results for SPG and well-known relatives such as the maximum-weight connected subgraph problem. These results include the strength of linear programming relaxations, polyhedral descriptions, and complexity results. We go on to introduce many algorithmic components such as reduction techniques, cutting planes, graph transformations, and heuristics-both for SPG and related problems. Many of these methods and techniques are provably stronger than previous results from the literature. For example, we introduce a new reduction concept that is strictly stronger than the well-known and widely used bottleneck Steiner distance. We also provide theoretical analyses (e.g. concerning complexity) of the new algorithms. The individual components are combined in an exact branch-and-cut algorithm. Notably, all problem classes can be handled by a single branch-and-cut kernel. As a result, we obtain an exact solver for SPG and 14 related problems. The new solver is on each of the 15 problem classes faster than all other (problem-specific) solvers from the literature, often by orders of magnitude. In particular, the solver outperforms the long-reigning state-of-the-art solver for SPG. Finally, many benchmark instances from the literature for several problem classes can be solved for the first time to optimality-some containing millions of edges. These problem classes include the SPG, the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem, and the Euclidean Steiner tree problem.
Das Steinerbaumproblem in Graphen (SPG) ist eines der am besten untersuchten Probleme der kombinatorischen Optimierung. Das große theoretische Interesse für das Problem kann auch darauf zurückgeführt werden, dass das SPG zwei weitere klassische Optimierungsprobleme verallgemeinert: Kürzeste Wege und Minimale Aufspannende Bäume. Auf der anderen (Praxis orientierten) Seite können viele Anwendungen in Industrie und Forschung als SPG oder verwandte Probleme modelliert werden. Das SPG hat in den letzten 10 Jahren beeindruckende theoretische Fortschritte erfahren. Im Gegensatz dazu hat es in der exakten SPG-Lösung seit fast 20 Jahren praktisch keinen Fortschritt gegeben. Wenngleich die DIMACS Challenge 2014 und die PACE Challenge 2018 neues Interesse für die exakte Lösung von SPGs in der Forschungsgemeinschaft weckten, blieben selbst die besten neuen Verfahren für SPG weit hinter der führenden Lösungstechnologie zurück. Diese Arbeit wurde mit dem Ziel gestartet, die exakte Lösung von SPGs nun erneut voranzubringen. Da viele praktische Anwendungen nicht als reine SPGs, sondern als eng verwandte Probleme modelliert werden, zielt diese Arbeit auch darauf ab, Fortschritte in der Lösung von SPGs mit Verbesserungen bei der exakten Lösung verwandter Probleme zu kombinieren. Die Arbeit beginnt mit dem Errichten eines breiten theoretischen Fundaments, auf welches die darauffolgenden algorithmischen Entwicklungen aufgebaut werden. So werden etwa verschiedene neue theoretische Ergebnisse für SPG und bekannte Verwandte wie das Maximum-Weight Connected Subgraph Problem eingeführt. Diese Ergebnisse beinhalten etwa Komplexitätsresultate für die betrachteten Probleme, oder stärkere polyedrische Beschreibungen des Lösungsraums. Anschließend werden diverse algorithmische Komponenten wie Reduktionstechniken, Schnittebenen, Graphentransformationen und Heuristiken vorgestellt - sowohl für SPG als auch für verwandte Probleme. Viele dieser Methoden und Techniken sind beweisbar stärker als bisherige Ergebnisse aus der Literatur. Weiterhin werden auch theoretische Analysen (z.B. bezüglich der Komplexität) der neuen Algorithmen gegeben. Die einzelnen Komponenten werden schließlich in einem exakten Branch-and-Cut- Algorithmus kombiniert. Herauszustellen ist, dass alle Problemklassen mit einem einzigen Branch-and-Cut Kern gelöst werden können. Das praktische Ergebnis dieser Arbeit ist ein exakter Löser für SPG und 14 weitere verwandte Probleme. Der neue Löser ist auf jeder dieser 15 Problemklassen schneller als alle anderen (problemspezifischen) Löser aus der Literatur, oft um Größenordnungen. Insbesondere liefert der neue Löser bessere Ergebnisse als der eingangs erwähnte bisher führende SPG Löser. Weiterhin können viele Benchmark-Instanzen aus der Literatur für mehrere Problemklassen zum ersten Mal gelöst werden - dies beeinhaltet Instanzen mit Millionen an Kanten. Zu diesen Problemklassen gehören das SPG, das prize-collecting SPG, das Maximum-Weight Connected Subgraph Problem und das Euklidische Steinerbaumproblem.