[Zurück]

A Chwatal:
"On the Minimum Label Spanning Tree Problem: Solution Methods and Applications";
Betreuer/in(nen), Begutachter/in(nen): G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2010; Rigorosum: 16.06.2010.

Das Minimum Label Spanning Tree Problem ist ein kombinatorisches Optimierungsproblem mit Anwendungen im Bereich des Designs von Telekommunikationsnetzwerken mit dem Ziel ein möglichst einheitliches Netzwerk hinsichtlich der verwendeten Übertragungseinrichtungen
zu finden. Gegeben ist ein zusammenhängender Graph, wobei jeder Kante
ein oder mehrere Label zugewiesen sind. Das Ziel ist die Bestimmung eines Spannbaumes welcher eine minimale Anzahl an Labels benötigt, sodass für jede gewählte Kante mindestens ein Label ausgewählt wird. Das Problem ist NP-vollständig.
Die bisherige Forschung in Bezug auf das gegebene Problem war primär auf die Entwicklung approximativer und metaheuristischer Algorithmen ausgerichtet, aber auch einige exakte Verfahren wurden vorgeschlagen. Es wurde gezeigt, dass kein polynomieller Algorithmus
mit konstantem Approximationsfaktor existieren kann (außer P = NP), jedoch sind heuristische und metaheuristische Algorithmen in der Lage hochqualitative Lösungen in angemessener Laufzeit zu finden. Exakte Verfahren können nur relativ kleine Probleminstanzen
zu lösen, jedoch kann die Entwicklung fortgeschrittener Methoden durchaus dazu in der Lage sein die Grenze der praktisch lösbaren Instanzen deutlich in Richtung größerer Instanzen zu verschieben, und somit deren praktische Anwendung zu ermöglichen.
In dieser Dissertation werden exakte und heuristische Methoden für das Minimum Label Spanning Tree Problem und einige seiner Varianten betrachtet. Bezüglich heuristischer Verfahren stellt die bisher noch nicht untersuchte Anwendung von Ant Colony
Optimization auf das gegebene Problem den Schwerpunkt dar. Weiters wird die Verwendung
der heuristischen Verfahren als primale Heuristik zur Beschleunigung exakter Verfahren
untersucht. Dann werden exakte Verfahren basierend auf gemischt-ganzzahliger
linearer Programmierung genauer betrachtet. Hierbei werden einerseits existierende Formulierungen
anhand neuer Klassen von gültigen Ungleichungen gestärkt, und des Weiteren neue Formulierungen vorgeschlagen. Weiters wird gezeigt wie fraktionale Lösungen der Relaxierung durch Weglassen der Ganzzahligkeitsbedingungen bezüglich der Label-
Variablen mittels Odd-Hole-Ungleichungen separiert werden können. Für letztere wird zur Verwendung in einem Schnittebenenverfahren eine heuristische Separierungsmethode
basierend auf einem gemischt-ganzzahligen Programm mit Miller-Tucker-Zemlin Ungleichungen
vorgestellt. Alle vorgestellten heuristischen und exakten Methoden wurden implementiert und mittels zahlreicher computationaler Tests ausgewertet. Die präsentierten Ergebnisse dokumentieren die Unterschiede zu bestehenden Verfahren, sowie die
erzielten Verbesserungen. Insbesondere stellt ein Branch-and-Cut Algorithmus basierend auf einer neuen Formulierung die eine schnelle Schnittebenen-Separierung ermöglicht eine
deutliche Verbesserung zu bestehenden exakten Verfahren dar. Die Anwendung der Odd-Hole Schnittebenen erweist sich für spezielle Instanzen als nützlich.
Der letzte Teil der Dissertation widmet sich einem neuen Ansatz zur Datenkompression, basierend auf Minimum Label Spanning Trees. Ziel ist die kompakte Repräsentation einer ungeordneten Menge von mehrdimensionalen Punkten. Der betrachtete Anwendungshintergrund
kommt aus der Biometrie, wo Fingerabdrücke oftmals durch deren charakteristische Punkte ("Minutien") dargestellt werden. Um diese Daten als zusätzliches
Sicherheitsmerkmal, z.B. in Reisepässen, verwenden zu können, werden spezielle Kompressionsverfahren
benötigt um diese als Wasserzeichen in Passbilder einbetten zu können.
Dafür kodieren wir eine Teilmenge der Minutien als Spannbaum, dessen Kanten wiederum
durch eine Referenz auf ein Element einer kleinen Menge an "Template-Arcs" und kleinen
Korrekturvektoren dargestellt werden. Dadurch werden geometrische Eigenschaften der
Punkte für die Kompression benutzt indem ein Baum mit möglichst ähnlichen Kanten
hinsichtlich der relativen Position von Anfangs- und Endknoten bestimmt wird. Dabei
entsprechen mögliche Template-Arcs einer Kante den Labels des Minimum Label Spanning
Tree Problems. Da nur eine Teilmenge der gegebenen Punkte an den Baum angeschlossen
wird, besteht ein weiterer Zusammenhang zum k-cardinality Tree Problem, welches ebenfalls
NP-schwer ist. Das resultierende Optimierungsproblem wird als k-node Minimum
Label Spanning Tree (k-MLSA) Problem bezeichnet.
Vor der Lösung des k-MLSA Problemes wird die Menge der Candidate Template-Arcs mittels eines Preprocessing-Schrittes von den Eingabedaten abgeleitet, was ebenfalls ein
nicht-triviales Problem darstellt. Zu diesem Zweck wird ein Algorithmus basierend auf begrenzter
Enumeration vorgestellt. Für das resultierende k-MLSA Problem werden Heuristiken
wie Greedy Randomized Adaptive Search Procedures oder Genetischen Algorithmen,
sowie exakten Verfahren wie Branch-and-Cut vorgschlagen. Weiters wird gezeigt, wie der
relativ zeitaufwändige Preprocessing-Schritt direkt in das Branch-and-Cut Verfahren integriert
werden kann, indem neue Template-Arcs während der Ausführung des Algorithmus
dynamisch zu einem ursprünglich eingeschränkten Modell hinzugefügt werden. Derartige
Ansätze sind bekannt als Branch-and-Cut-and-Price. Das Pricing-Problem entspricht der
Bestimmung einer Template-Arc Variable welche die Zielfunktion potentiell verbessern
kann, und wird anhand eines Algorithmus basierend auf einer k-d Tree Datenstruktur
gelöst. Computationale Tests belegen die Eignung des präsentierten Kompressionsmodelles
für die vorgeschlagene Anwendung. Darüber hinaus kann es als Ausgangspunkt
für weitere Untersuchungen hinsichtlich der Kompression von intrinsisch ungeordneten
Datenmengen, wie zum Beispiel ungleich verteilten Messwerten, dienen.

The minimum label spanning tree problem is a combinatorial optimization problem with
applications in telecommunication network design with the goal of deriving a network that
is preferably uniform w.r.t. to the used communication facilities. For the minimum label
spanning tree problem we are given a connected graph with labels associated to its edges.
The goal is to derive a spanning tree requiring a minimum amount of labels in the sense
that for each edge an according label must be selected. The problem has been shown to be NP-complete.
So far, research has primarily been devoted to the development and analysis of approximation algorithms and heuristics, but also some exact solution methods have been proposed.
It has been shown that no polynomial constant-factor approximation algorithms do exist (unless P = NP), but however, heuristic and metaheuristic algorithms are able to provide
high quality solutions within a reasonable amount of computation time. Exact methods are only capable of solving relatively small instances in practice, but the development of
elaborate methods may significantly shift the border of exactly solvable instances towards
larger ones, enabling their application for practical purposes.
Within this thesis exact and heuristic methods for the minimum label spanning tree problem
and some variations are investigated. Regarding metaheuristics, main emphasis is given to the application of ant colony optimization, which has not yet been considered for the given problem. Moreover, it is studied how these methods can be used as primal
heuristics to speed up exact solution methods. In the following, exact methods based on mixed integer programming are investigated. Within this context existing formulations are
strengthened by new classes of inequalities and new formulations are proposed. In particular it is shown how odd-hole inequalities can be used to cut-off fractional label solutions
in order to tighten the linear programming relaxation. For the latter ones a heuristic separation procedure based on a mixed integer linear program using Miller-Tucker-Zemlin
inequalities is proposed, to be used within a cutting-plane algorithm. All the presented heuristic and exact methods have been implemented and evaluated by comprehensive computational experiments. Reported computational results show the differences and improvements
to existing methods. In particular the branch-and-cut algorithm based on the new connectivity formulation, which enables a fast cutting-plane separation, significantly
outperforms all existing exact methods. The application of odd-hole cutting-planes turned
out to be beneficial for particular classes of instances.
The last part of this thesis is dedicated to a newly developed compression model, which
is primarily based on the minimum label spanning tree problem. The particular goal is to derive a compact representation of a set of unordered multi-dimensional points. The
considered application scenario comes from the field of biometrics, where fingerprint data is often encoded as a set of characteristic points ("minutiae") of the fingerprint pattern. In
order to use this data as an additional security feature e.g. in passports, strong compression is required to be able to embed this data into images by watermarking techniques. For this
purpose a subset of the minutiae is encoded by a spanning tree, whose edges are in turn represented by references into a small set of "template arcs" and small correction vectors.
By this approach it is possible to extract geometric structure within the given points and obtain compression by deriving a tree that contains a maximum number of arcs that are
similar w.r.t. the relative geometric position of their incident nodes. By identification of the template arcs with labels we obtain the correspondence to a variant of the minimum
label spanning tree problem. As only a subset of nodes is required to be connected, the problem is also related to the k-cardinality tree problem, which is also NP-hard. We call the resulting optimization problem k-node minimum label arborescence (k-MLSA) problem.
Prior to solving the k-MLSA problem a set of candidate template arcs needs to be derived in a preprocessing step from the input data, which is itself a non-trivial task. For this purpose an algorithm based on restricted enumeration is proposed. For the resulting
k-MLSA problem heuristic methods including greedy randomized adaptive search procedures and genetic algorithms as well as exact methods including branch-and-cut are proposed. Finally it is shown, how the relatively time-consuming preprocessing step can
be directly incorporated into the branch-and-cut algorithm by dynamically adding new promising template arcs to the initially restricted model during the branch-and-cut algorithm.
Such approaches are well known as branch-and-cut-and-price. The pricing problem, i.e. the determination of a template arc variable potentially improving the current objective function, is solved by an algorithm based on a k-d tree data structure. The presented
compression model is shown to be beneficial for the outlined application background, but may also serve as source for further investigations into the direction of compression models
that benefit from intrinsically unordered data sets like for instance unequally distributed scientific measurements.

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