[Back]

M. Gruber:
"Exact and Heuristic Approaches for Solving the Bounded Diameter Minimum Spanning Tree Problem";
Supervisor, Reviewer: G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2009; oral examination: 2009-06-16.

The bounded diameter minimum spanning tree (BDMST) problem is a combinatorial
optimization problem appearing in applications such as wire-based communication
network design when quality of service is of major concern and, for example, a
signal between any two nodes in the network should not pass more than a fixed
number of routers. It also arises in ad-hoc wireless networks and in the areas of data
compression and distributed mutual exclusion algorithms.
Given an undirected, weighted, and connected graph G = (V,E) with a node set V
and an edge set E the goal is to identify a tree structure of minimum costs connecting
all nodes of this network where the number of edges on each path linking any pair of
nodes is limited by a maximum diameter D. This problem is known to be NP-hard
for a diameter bound of 4 ≤ D < |V | − 1.
There exist a great variety of different approaches to solve this problem. Beside
models based on Miller-Tucker-Zemlin inequalities especially multi-commodity hop-
indexed flow formulations have proven to be very successful in exactly solving the
BDMST problem. However, to obtain tight linear programming (LP) relaxation
bounds these models require a huge number of variables. Due to the complexity of
the problem exact approaches are limited to relatively small instances with clearly
less than 100 nodes when considering complete graphs. Therefore, heuristics have
been developed to solve instances with up to 1000 and more nodes. Fast and sim-
ple greedy construction heuristics are primarily based on Prim´s minimum spanning
tree algorithm, but in particular on Euclidean instances this greedy behavior mis-
leads these heuristics since in this case in general also long edges are part of a
good BDMST. For higher quality solutions metaheuristics, especially evolutionary
algorithms, have been proposed.
vii
Abstract
In this thesis, various new approaches are presented to solve moderately sized
instances of the BDMST problem to proven optimality, as well as constructing
diameter-constrained trees on larger instances of significantly higher quality than
it was possible before.
First, five local search neighborhood structures are defined to locally improve (in-
termediate) trees computed with one of the proposed algorithms. Since they are
based on three different representations of a solution they complement each other
in a perfect way. Special attention is payed on the efficient evaluation of solutions
and moves when searching these neighborhoods.
Two different exact integer linear programming models for the BDMST problem
are introduced trying to overcome the main problem of the multi-commodity flow
formulations, i.e., the great number of required variables. A simple and compact
0-1 integer linear programming (ILP) model is further strengthened by dynamically
adding violated connection and cycle elimination constraints within a Branch&Cut
environment. The second model is based on so-called jump inequalities to ensure
the diameter bound. Again, Branch&Cut is utilized due to the fact that the number
of these jump inequalities grows exponentially with |V |. Since identifying a violated
jump inequality for a fractional LP solution is conjectured to be NP-hard a hierarchy
of (meta-)heuristics is used to solve this separation problem efficiently.
For larger instances three different metaheuristics are proposed making use of the
defined neighborhoods. They are utilized by local improvement strategies within
a variable neighborhood search (VNS), an evolutionary algorithm (EA) utilizing a
new encoding of solutions, and an ant colony optimization (ACO). Finally, a new
fast construction heuristic based on clustering is presented designed especially for
Euclidean instances.
The computational results demonstrate the efficiency of the discussed approaches.
Using the ILP model based on jump inequalities it was possible to discover so long
unknown optima for various problem instances, and to compete with state-of-the-
art hop-indexed multi-commodity flow formulations, especially when the diameter
bound is loose. For larger instances with hundreds of nodes, the ACO is currently
the leading metaheuristic to get high-quality solutions within reasonable time. In
the end, also the new construction heuristic outperforms standard algorithms from
the literature significantly on very large Euclidean instances.

Das Finden eines durchmesserbeschränkten minimale Spannbaumes (bounded dia-
meter minimum spanning tree, BDMST) ist ein kombinatorisches Optimierungspro-
blem aus dem Bereich des Netzwerkdesigns und hat Anwendungen in verschiedensten
Bereichen. So unter anderem beim Entwurf von kabelgebundenen Kommunikations-
netzwerken, sofern gewisse Anforderungen hinsichtlich der Kommunikationsgüte
erfüllt werden sollen. Um die Wahrscheinlichkeit für das Auftreten von Störun-
gen möglichst gering zu halten, soll zum Beispiel ein Signal über weniger als eine
festgelegte Anzahl an Routern laufen. Aber auch bei ad-hoc Funknetzwerken oder
bei der Datenkomprimierung sowie bei verteilten Mutual Exclusion Algorithmen gilt
es immer wieder, einen BDMST zu berechnen.
Bei dieser Problemstellung gilt es, in einem ungerichteten, gewichteten und zusam-
menhängenden Graphen G = (V,E) mit der Knotenmenge V und der Kantenmenge
E einen aufspannenden Baum minimaler Kosten zu finden. Zusätzlich muss gelten,
dass die Anzahl der Kanten auf jedem Pfad zwischen zwei beliebigen Knoten inner-
halb des Baumes kleiner oder gleich einem Durchmesser D ist. Dieses Problem ist
für eine Durchmesserbeschränkung von 4 ≤ D < |V | − 1 NP-schwer.
Es existiert eine Vielzahl verschiedener Verfahren, um dieses Problem zu lösen. Für
eine exakte Lösung des BDMST Problems haben sich neben Modellen, die auf Miller-
Tucker-Zemlin Ungleichungen aufbauen, besonders spezielle Flussformulierungen
als sehr erfolgreich herausgestellt. Während die mit diesen Modellen erhaltenen
Schranken sehr gut sind, ist die Anzahl der benötigten Variablen sehr groß. Aufgrund
der Komplexität des Problems ist die Anwendbarkeit exakter Verfahren auf relativ
kleine Instanzen mit nicht mehr als 100 Knoten beschränkt, sofern von vollständigen
Graphen ausgegangen wird. Um Instanzen mit 1000 und mehr Knoten (zumindest
näherungsweise) lösen zu können, wurden auch verschiedene Heuristiken entwick-
elt. Einfachen, aber schnellen Konstruktionsheuristiken basieren auf dem Algorith-
mus von Prim zum Finden eines minimalen Spannbaumes (minimum spanning tree,
MST). Da diese aber aufgrund sehr lokal getroffener Entscheidungen speziell auf
euklidischen Graphen im Normalfall versagen, da hier durchaus auch längere Kan-
ten Teil einer guten Lösung sein können, wurden auch Metaheursitiken eingesetzt -
hauptsächlich evolutionäre Algorithmen (evolutionary algorithms, EAs).
In dieser Dissertation werden neben neuen Verfahren, um Instanzen des BDMST
Problems moderater Größe beweisbar optimal zu lösen, auch Algorithmen
vorgestellt, um auf größeren Instanzen durchmesserbeschränkte Spannbäume in einer
Qualität zu berechnen, die bisher nicht möglich war.
Basierend auf drei unterschiedlichen Lösungsrepräsentationen werden fünf, sich
gegenseitig ergänzende Nachbarschaftsstrukturen definiert, die dazu verwendet wer-
den, um aus gegebenen Bäumen jeweils neue, bessere Lösungen zu generieren. Um
ein möglichst effizientes Durchsuchen der Nachbarschaften zu realisieren, wird hier
großes Augenmerk auf eine inkrementelle Auswertung dieser gelegt.
Zwei Formulierungen des BDMST Problems als ganzzahlige lineare Programme (in-
teger linear programs, ILPs) werden vorgestellt, die versuchen, das Hauptproblem
der Flussformulierungen, die große Anzahl an Variablen, zu vermeiden. Ein ein-
faches und kompaktes 0-1 ILP Modell wird, eingebettet in einen Branch&Cut Al-
gorithmus, durch das dynamische Hinzufügen verletzter Ungleichungen zur Sicher-
stellung der Konnektivität und der Kreisfreiheit zusätzlich gestärkt. Das zweite
Modell basiert auf sogenannten
"jump inequalities", Nebenbedingungen, die die
Durchmesserbeschränkung sicherstellen. Da ihre Anzahl exponentiell mit der Kno-
tenanzahl |V | steigt, kommt auch hier ein Branch&Cut Verfahren zum Einsatz.
Da das Identifizieren einer verletzten
"jump" Nebenbedingung in einer fraktionalen
Lösung des zugehörigen linearen Programms mutmaßlich NP-schwer ist, wird eine
Hierarchie von (Meta-)Heursitiken eingesetzt, um dieses Separierungsproblem ef-
fizient zu lösen.
Für größere Instanzen werden drei unterschiedliche Metaheuristiken vorgestellt,
die auf den für das BDMST Problem definierten Nachbarschaften aufbauen.
Diese werden als lokale Verbesserungsstrategien innerhalb einer variablen Nach-
barschaftssuche (variable neighborhood search, VNS), eines evolutionären Algorith-
mus mit einer neuen Lösungsrepräsentation, und einem Ameisensystem (ant colony
optimization, ACO) eingesetzt. Zu guter Letzt wird noch eine neue Konstruktion-
sheuristik präsentiert, die auf einem Clustering der Knoten basiert und speziell für
große euklidische Instanzen geeignet ist.
Die Testergebnisse zeigen eindrucksvoll die Effizienz der hier beschriebenen Ver-
fahren. Mit Hilfe des ganzzahligen linearen Programms auf Basis der
"jump in-equalities" konnte für mehrere bisher nicht exakt lösbare Instanzen das Optimum bestimmt werden. Besonders bei größeren Durchmessern ist dieser Ansatz auch
den sehr erfolgreichen Flussformulierungen überlegen. Für Instanzen mit mehreren
hundert Knoten ist der vorgestellte ACO die zur Zeit führende Metaheuristik, um
qualitativ hochwertige Lösungen in vernünftiger Zeit zu berechnen. Schlussendlich
liefert die hier präsentierte Konstruktionsheuristik für sehr große euklidische In-
stanzen durchmesserbeschr¨ankte Spannbäume mit einer Lösungsgüte, die bisherige
Verfahren aus der Literatur besonders bei kleinen Durchmessern bei weitem nicht
erreichen konnten.

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