[Zurück]

M. Ruthmair:
"On Solving Constrained Tree Problems and an Adaptive Layers Framework";
Betreuer/in(nen), Begutachter/in(nen): G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2012; Rigorosum: 21.06.2012.

Die vorliegende Arbeit behandelt ausgewählte kombinatorische Optimierungsprobleme im Bereich
des Netzwerkdesigns. In vielen dieser Probleme kommuniziert ein zentraler Server mit einer
Gruppe von Clients, wobei es üblicherweise das Ziel ist, kostenminimaleWege im Netzwerk
zu finden. Neben diesem Optimierungsziel erfordern aktuelle Anwendungen, z.B. im Multimedia-
Bereich, die Einhaltung weiterer sogenannter Quality-of-Service Bedingungen, die unter anderem
in der Beschränkung der Übertragungszeit zwischen Server und Clients bestehen. Diese
Art von Problemen kann oft auf einem Graph modelliert werden, wobei eine optimale Lösung
meistens einem Baum entspricht, der den Server und alle Clients beinhält und alle geforderten
Nebenbedingungen erfüllt. Die wichtigsten dieser Probleme sind jedoch NP-schwer, was dazu
führt - vorausgesetzt P 6= NP -, dass aufwendige und raffinierte Verfahren gefunden werden
müssen, um gute bzw. optimale Lösungen zu erhalten.
Aufgrund der Komplexität dieser Optimierungsprobleme ist es üblicherweise nicht möglich
beweisbar optimale Lösungen für größere Probleminstanzen in angemessener Zeit zu finden.
Deshalb verwendet man in der Praxis oft heuristische Ansätze, die zwar im Allgemeinen nur
zu suboptimalen aber dennoch zu sehr guten Lösungen führen. Metaheuristiken und hybride
Varianten, die heuristische und exakte Verfahren kombinieren, gewannen in den letzten Jahren
immer mehr an Beliebtheit, da sie für eine Vielzahl von wichtigen Optimierungsproblemen bereits
überaus erfolgreiche Resultate erzielt haben.
Wir präsentieren neue State-of-the-Art Ansätze um einige dieser Probleme zu lösen, wobei
wir zu allererst versuchen die gegebene Probleminstanz zu reduzieren, in dem wir Knoten und
Kanten identifizieren, die entweder in keiner oder nur in einer suboptimalen Lösung enthalten
sein können, und entfernen diese dann aus dem Graph. Je mehr der Graph in dieser Phase reduziert
werden kann, desto einfacher ist es üblicherweise eine gültige oder optimale Lösung zu
finden.
Für das sogenannte Rooted Delay-Constrained Minimum Spanning Tree (RDCMST) Problem,
in dem alle Knoten in einem Graph mit dem vorgegebenen Wurzelknoten verbunden
werden müssen und das Gesamtdelay jedes Pfads vom Server zu einem Client eine maximale
Schranke nicht überschreiten darf, haben wir verschiedene heuristische Ansätze entwickelt. Um
eine gültige Lösung zu konstruieren, wenden wir Heuristiken an, die auf Kruskal´s Algorithmus
zum Finden eines minimalen Spannbaums oder dem Multilevel-Refinement-Paradigma basieren.
Weitere Verbesserungen dieser Lösungen werden durch folgende Verfahren erzielt: einer
Greedy-Randomized-Adaptive-Search-Procedure, einer lokalen Suche in verschiedenen Nachbarschaftsstrukturen
und der Einbettung dieser in einer variablen Nachbarschaftssuche, eines
Ant-Colony-Optimization Ansatzes und eines genetischen Algorithmus. Das Vorkommen von
Duplikaten im genetischen Algorithmus wird diskutiert und entsprechende Verfahren werden
vorgestellt, um mit diesen geeignet umzugehen. Experimentelle Ergebnisse haben schließlich
die Überlegenheit des evolutionären Ansatzes und der variablen Nachbarschaftssuche gegenüber
den restlichen Methoden gezeigt.
Zusätzlich zu diesen (meta-)heuristischen Ansätzen versuchen wir kleinere bis mittelgroße
Probleminstanzen exakt zu lösen, wobei wir uns hier hauptsächlich auf Methoden der mathematischen
Programmierung konzentrieren, die sich in einer Vielzahl von existierenden Arbeiten zu
Netzwerkdesignproblemen als überaus erfolgreich gezeigt haben. Speziell die Modellierung dieser
Probleme auf einem sogenannten Layered-Graph haben besonders gute Ergebnisse erzielt.
Anhand des Rooted Delay-Constrained Steiner Tree (RDCST) Problems, das eine Generalisierung
des RDCMST Problems darstellt, in der nur eine Untermenge der vorhandenen Knoten an
denWurzelknoten angeschlossen werden muss, vergleichen wir verschiedene Modellierungsansätze.
Die experimentellen Resultate zeigen, dass drei Methoden die restlichen übertreffen: ein
Branch-and-Price Ansatz, der durch die Verwendung von alternativen dual-optimalen Lösungen
beschleunigt wird, ein Modell auf einem entsprechenden Layered-Graph und eine Formulierung,
die eine exponentielle Anzahl von Subtour-Eliminations- und verbesserten Pfadungleichungen
enthält.
In manchen Situation, z.B. in Voice-over-IP-Anwendungen, ist es nicht nur wichtig, dass
alle Empfänger die Informationen innerhalb einer gewissen Zeitspanne erhalten, sondern auch
ungefähr zur gleichen Zeit. Diese zusätzliche Bedingung wird im sogenannten Rooted Delayand
Delay-Variation-Constrained Steiner Tree (RDDVCST) Problem modelliert, wobei wir hier
Integer-Programming-Formulierungen basierend auf Informationsflüssen bzw. einem Layered-
Graph vergleichen. Der letztere der beiden Ansätze, erweitert durch stärkende Ungleichungen,
erwies sich gegenüber dem Flussmodell als weit überlegen.
Die praktische Anwendbarkeit der Layered-Graph-Ansätze ist teilweise eingeschränkt, da
deren Effizienz stark von der Menge der realisierbaren Pfaddelays und der gegebenen Zeitschranken
abhängt. Deshalb haben wir diese Methoden zu einem generellen iterativen Adaptive
Layers Framework (ALF) erweitert, das die Nachteile dieser Ansätze teilweise abschwächt und
dennoch von deren Stärken profitiert. Im Grunde approximiert ALF eine optimale Lösung des
ganzzahligen Modells und dessen fraktionaler Relaxierung auf dem kompletten Layered-Graph
durch das Lösen einer Serie von üblicherweise viel kleineren Modellen, und kann dadurch teilweise
die Probleme mit sehr großen Layered-Graphen vermeiden. Wie die Ergebnisse zeigen,
lohnt sich der zusätzliche Aufwand für das wiederholte Lösen von Modellen in vielen Fällen,
wobei speziell auf großen dünnen Graphen ALF alle anderen Ansätze für das RDCST Problem
klar aussticht. Zusätzlich führen wir noch zwei Fallstudien auf anderen Problemen an: Für eine
erweiterte Variante des RDCST Problems mit Berücksichtigung von Profiten auf Knoten und einer
Quotenbedingung zeigte sich ALF in vielen Fällen sogar um Größenordnungen besser. In der
zweiten Fallstudie betrachten wir das Vehicle Routing Problem with Time Windows und diskutieren
ein Modell auf zwei getrennten Layered-Graphen und ein weiteres auf einem dreidimensionalen
Layered-Graph. Erste Ergebnisse belegen, dass diese Ansätze durchaus vielversprechend
erscheinen.

In this thesis we consider selected combinatorial optimization problems arising in the field of
network design. In many of these problems there is a central server sending out information to a
set of recipients. A common objective is then to choose connections in the network minimizing
the total costs. Besides this, current applications, e.g. in multimedia, usually force additional
quality-of-service constraints, e.g. limiting the communication delay between the central server
and the clients. In general, these problems can be modeled on a graph and in many cases an
optimal solution corresponds to a rooted tree with minimum costs satisfying all the given constraints.
The most relevant of these optimization problems are NP-hard making it necessary -
provided that P 6= NP - to develop sophisticated algorithmic approaches to obtain high quality
or even optimal solutions.
Due to the complexity of these optimization problems it is usually not possible to obtain
proven optimal solutions for medium- to large-sized problem instances in reasonable time.
Therefore, heuristic approaches yielding high quality but in general sub-optimal solutions are
of high practical interest. Metaheuristics and hybrid variants combining heuristic and exact solution
techniques recently increased in popularity due to their successful application on many
important optimization problems.
We present new state-of-the-art solution approaches for several of these optimization problems.
Given a problem instance we first apply reduction rules identifying and removing nodes
and edges in the graph which can only be part of infeasible or sub-optimal solutions. The more
the input graph can be reduced in this way a priori the easier it is in general for an algorithm to
find a feasible or optimal solution.
We designed several heuristic approaches for the rooted delay-constrained minimum spanning
tree (RDCMST) problem in which all nodes in a graph have to be connected to a fixed root
node while the total delay on the paths from the root to any other node has to be within a given
delay-bound. For constructing a feasible solution we suggest a heuristic based on Kruskal´s
minimum spanning tree algorithm and another one utilizing the multilevel refinement paradigm.
Improvements to these obtained solutions are achieved by applying a greedy randomized adaptive
search procedure, local search in two different neighborhood structures, and embedding this
local search in a general variable neighborhood search, an ant colony optimization approach,
and a genetic algorithm. The appearance of duplicate solutions within the genetic algorithm is
discussed and appropriate methods dealing with them are presented. Extensive computational results
indicate the superiority of the evolutionary approach and the variable neighborhood search.
Additionally, we tackled small- to medium-sized problem instances with exact algorithms,
mostly concentrating on mathematical programming methods since these turned out to perform
well on numerous related network design problems in the literature. Especially modeling these
problems on so-called layered graphs has been shown to yield good results. We compared
different modeling approaches for the rooted delay-constrained Steiner tree (RDCST) problem
which is a generalization of the RDCMST problem where only a subset of the nodes is required
to be connected to the root node. Computational results indicate that three methods dominate the
comparison: a branch-and-price approach stabilized by using alternative dual-optimal solutions,
a model on a corresponding layered graph, and a formulation based on an exponential number
of subtour elimination and infeasible path inequalities.
In some situations, e.g. in Voice-over-IP applications, it is not only important that all recipients
receive the information within a given delay-bound but also nearly at the same time. This
additional constraint is modeled in the rooted delay- and delay-variation-constrained Steiner
tree (RDDVCST) problem. For this problem we compare mixed integer programming formulations
based on multi-commodity flows and again a transformation to a layered graph. The latter
approach extended by some valid inequalities turned out to be clearly superior to the flow-based
model.
Since the performance of layered graph approaches strongly depends on the sizes of the set of
achievable path delay values and on given delay-bounds their practical applicability is limited.
Thus, we extend these methods to a generally-applicable iterative adaptive layers framework
(ALF) mitigating their disadvantages and emphasizing their benefits. Basically, ALF approximates
the linear programming relaxation and the optimal integer solution of a complete layered
graph formulation by solving a sequence of usually much smaller models and thus partly overcomes
possible problems with huge layered graphs. The additional overhead of repeated model
solving pays off in many cases, as experimental results indicate, especially on large sparse graphs
ALF outperforms all other approaches for the RDCST problem. Additionally, we provide two
case studies on applying ALF to further problems: For an extended variant of the RDCST problem
with consideration of node prizes and a quota constraint ALF is clearly superior to other
methods, in many cases even by orders of magnitudes. The second case study considers the
vehicle routing problem with time windows: Here, we discuss a modeling approach on two separated
layered graphs and another one on a three-dimensional layered graph. Preliminary results
indicate that futher work in this direction is promising.

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