Faster algorithms for Steiner tree
and related problems:
From theory to practice
vorgelegt von
M. Sc.
Daniel Markus Rehfeldt
ORCID: 0000-0002-2877-074X
von der Fakult¨at II – Mathematik und Naturwissenschaften
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
– Dr. rer. nat. –
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Dietmar H¨omberg
Gutachter: Prof. Dr. Thorsten Koch
Gutachter: Prof. Dr. Eduardo Uchoa
Gutachter: Dr. Renato Werneck
Tag der wissenschaftlichen Aussprache: 16. August 2021
Berlin 2021
Abstract
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 out-
performs 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.
i
Zusammenfassung
Das Steinerbaumproblem in Graphen (SPG) ist eines der am besten untersuchten
Probleme der kombinatorischen Optimierung. Das große theoretische Interesse f¨ur das
Problem kann auch darauf zur¨uckgef¨uhrt werden, dass das SPG zwei weitere klassische
Optimierungsprobleme verallgemeinert: K¨urzeste Wege und Minimale Aufspannende
B¨aume. Auf der anderen (Praxis orientierten) Seite k¨onnen viele Anwendungen in
Industrie ond 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¨osung seit fast 20 Jahren praktisch
keinen Fortschritt gegeben. Wenngleich die DIMACS Challenge 2014 und die PACE
Challenge 2018 neues Interesse f¨ur die exakte L¨osung von SPGs in der Forschungsge-
meinschaft weckten, blieben selbst die besten neuen Verfahren f¨ur SPG weit hinter
der f¨uhrenden L¨osungstechnologie zur¨uck.
Diese Arbeit wurde mit dem Ziel gestartet, die exakte L¨osung von SPGs nun
erneut voranzubringen. Da viele praktische Anwendungen nicht als reine SPGs, son-
dern als eng verwandte Probleme modelliert werden, zielt diese Arbeit auch darauf ab,
Fortschritte in der L¨osung von SPGs mit Verbesserungen bei der exakten L¨osung ver-
wandter Probleme zu kombinieren. Die Arbeit beginnt mit dem Errichten eines breiten
theoretischen Fundaments, auf welches die darauffolgenden algorithmischen Entwick-
lungen aufgebaut werden. So werden etwa verschiedene neue theoretische Ergebnisse
f¨ur SPG und bekannte Verwandte wie das Maximum-Weight Connected Subgraph
Problem eingef¨uhrt. Diese Ergebnisse beinhalten etwa Komplexit¨atsresultate f¨ur die
betrachteten Probleme, oder st¨arkere polyedrische Beschreibungen des L¨osungsraums.
Anschließend werden diverse algorithmische Komponenten wie Reduktionstechniken,
Schnittebenen, Graphentransformationen und Heuristiken vorgestellt - sowohl f¨ur
SPG als auch f¨ur verwandte Probleme. Viele dieser Methoden und Techniken sind be-
weisbar st¨arker als bisherige Ergebnisse aus der Literatur. Weiterhin werden auch the-
oretische Analysen (z.B. bez¨uglich der Komplexit¨at) 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¨ost werden k¨onnen.
Das praktische Ergebnis dieser Arbeit ist ein exakter L¨oser f¨ur SPG und 14
weitere verwandte Probleme. Der neue L¨oser ist auf jeder dieser 15 Problemklassen
schneller als alle anderen (problemspezifischen) L¨oser aus der Literatur, oft um
Gr¨oßenordnungen. Insbesondere liefert der neue L¨oser bessere Ergebnisse als der
iii
Loading more pages...