[Back]

K. Oberlechner:
"Solving the k-node minimum label spanning arborescence problem with exact and heuristic methods";
Supervisor: G. Raidl, A Chwatal; Institut für Computergraphik und Algorithmen, 2010; final examination: 2010-08.

In this thesis, exact and heuristic methods for solving the k-node minimum label spanning arborescence
(k-MLSA) problem are developed. The k-MLSA problem is a combination of the minimum label
spanning tree problem and the k-cardinality tree problem, which are both NP-complete. Given a complete,
directed graph in which one or more labels are associated with each arc, the goal is to derive a
minimum cardinality subset of labels such that their corresponding arcs contain a directed tree connecting
at least k nodes of the graph. The problem arises in the context of a data-compression model,
which has been developed as part of a project at the Institute of Computer Graphics and Algorithms
(Vienna University of Technology). In addition to exact and heuristic methods for solving the k-MLSA
problem, this thesis contributes a new preprocessing algorithm for constructing the initial labels.
The heuristic method is a memetic algorithm (MA), i.e. a combination of a genetic algorithm with
local search methods, which are used to further improve candidate solutions derived by the evolutionary
operators. The exact algorithm is based on mathematical programming. It solves the underlying
integer programming formulation by combining branch-and-cut with column generation in a branchand-
cut-and-price (BCP) approach. In this approach, new (label) variables and constraints are added
dynamically to an incomplete initial model during the branch-and-bound process. The new variables
are generated by solving the pricing problem, which is based on the values of the dual variables of the
current solution. Hence, the label variables no longer need to be constructed in a preprocessing step.
As the pricing problem needs to be solved frequently as part of the overall BCP process, efficient algorithms
are required. For this purpose, a method based on non-dominated interval search is proposed.
It provides an efficient solution to the pricing problem as well as to the preprocessing step.
The BCP approach proposed in this thesis can solve larger instances than previously developed
branch-and-cut and branch-and-price algorithms. However, for practical applications, the MA is more
appropriate as it is able to find near-optimal solutions for larger instances within short running times.
The new preprocessing method significantly reduces computational complexity compared to the previous
method, which has been the bottleneck in the overall procedure.

In dieser Diplomarbeit werden exakte und heuristische Methoden entwickelt um das k-node Minimum
Label Spanning Arborescence (k-MLSA) Problem zu lösen. Dieses Problem ist eine Kombination
des Minimum Label Spanning Tree (MLST) Problems und des k-cardinality Tree Problems, die
beide NP-vollständig sind. Beim MLST Problem soll in einem gerichteten Graphen, dessen Kanten
ein oder mehrere Label zugeordnet sind, die minimale Teilmenge an Labels gefunden werden,
sodass die entsprechenden Kanten einen gerichteten Baum mit zumindest k Knoten des Graphen enthalten.
Dieses Problem ergibt sich im Kontext eines laufenden Projektes am Institut für Computer Graphik und Algorithmen (Technische Universität Wien), in dem ein neuer graphenbasierter Ansatz
zur Datenkompression entwickelt wurde. Neben den exakten und heuristischen Methoden zur Lösung des k-MLSA Problems wird in dieser Diplomarbeit ein neuer Preprocessing Algorithmus entwickelt
um die initialen Labels zu erzeugen.
Die entwickelte Heuristik ist ein memetischer Algorithmus (MA), d.h. die Kombination eines
genetischen Algorithmus mit lokalen Suchmethoden, die dazu dienen die mittels evolutionärer Operatoren
gefundenen Kandidatenlösungen weiter zu verbessern. Der exakte Algorithmus basiert auf
Methoden der mathematischen Programmierung. Zur Lösung des zugrundeliegenden ganzzahligen
linearen Modells werden Branch-and-Cut und Spalten Generierung zu einem Branch-and-Cut-and-Price (BCP) Algorithmus verbunden. Dieser Algorithmus erzeugt neue (Label) Variablen und Nebenbedingungen
dynamisch während des Branch-and-Bound Prozesses, und fügt diese zu einem ursprünglich unvollständigen Modell hinzu. Die neuen Variablen werden erzeugt indem das Pricing Problem basierend auf den Werten der dualen Variablen der jeweiligen Lösung berechnet wird. In diesem
Ansatz müssen die (Label) Variablen nicht mehr in einem Preprocessing Schritt generiert werden. Da
das Pricing Problem im Verlauf des BCP Prozesses häufig gelöst werden muss, erfordert es besonders effiziente Algorithmen. Zu diesem Zweck wird eine Methode vorgestellt, die auf der Suche von nicht
dominierten Intervallen basiert und effiziente Lösungen sowohl für das Pricing Problem als auch für den Preprocessing Schritt generieren kann.
Obwohl die in dieser Diplomarbeit vorgestellte BCP Methode grössere Instanzen in kürzerer Zeit lösen kann als die schon entwickelten Branch-and-Cut und Branch-and-Price Algorithmen ist für
praktische Anwendungen der MA geeigneter, da dieser fast optimale Lösungen für grössere Instanzen in sehr kurzer Zeit findet. Die neue Preprocessing Methode reduziert die Berechnungskomplexiät im
Vergleich zur früheren Methode, die einen Flaschenhals im Verfahren bildete, signifikant.

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