On the minimum label spanning tree problem : solution methods and applications

Abstract

Das Minimum Label Spanning Tree Problem ist ein kombinatorisches Optimierungsproblem mit Anwendungen im Bereich des Designs von Telekommunikationsnetzwerken. 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. Dabei muss für jede gewählte Kante mindestens ein Label ausgewählt werden. Das Problem ist NP-vollständig.<br />Die bisherige Forschung in Bezug auf das gegebene Problem war primär auf die Entwicklung approximativer und metaheuristischer Algorithmen ausgerichtet, aber auch exakte Verfahren wurden vorgeschlagen. Es wurde gezeigt, dass kein polynomieller Algorithmus mit konstantem Approximationsfaktor existieren kann (außer wenn 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 lösbaren Instanzen deutlich in Richtung größerer Instanzen zu verschieben, und somit deren praktische Anwendung zu ermöglichen.<br />In dieser Dissertation werden exakte und heuristische Methoden für das Minimum Label Spanning Tree Problem und einige seiner Varianten betrachtet. Insbesondere wird die Anwendung von Ant Colony Optimization auf das Problem vorgestellt. Weiters werden exakte Verfahren basierend auf gemischt-ganzzahliger Programmierung betrachtet. In diesem Kontext werden sowohl bestehende Formulierungen anhand neuer Klassen von Ungleichungen gestärkt, als auch neue Formulierungen vorgeschlagen.<br />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. Ergebnisse der umfangreichen computationalen Tests dokumentieren die Unterschiede zu bestehenden Verfahren, sowie die erzielten Verbesserungen.<br />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 ist die Kompression von Fingerabdrucksdaten um diese als weiteres Sicherheitsmerkmal in Form von Wasserzeichen in Passbildern einbetten zu können. Angewandte Methoden umfassen sowohl Metaheuristiken wie memetische Algorithmen und Greedy Randomized Adaptive Search Procedures als auch exakte Verfahren wie Branch-and-Cut und Branch-and-Cut-and-Price. Testergebnisse belegen die Eignung des vorgestellten Ansatzes zur Lösung des betrachteten Problems.<br />

The minimum label spanning tree problem is a combinatorial optimization problem with applications in telecommunication network design. 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 at least one according label must be selected. The problem has been shown to be NP-complete.<br />So far, research regarding the considered problem has primarily been devoted to the development and analysis of approximation algorithms and heuristics, but also certain exact methods have been proposed. It has been shown that no polynomial-time constant-factor approximation algorithm does exist (unless P=NP), but however, heuristic and metaheuristic algorithms are able to provide high quality solutions within a reasonable amount of computation time in practice. Exact methods are only capable of solving relatively small instances, but the development of elaborate methods may significantly shift the border of exactly solvable instances towards larger ones, enabling their application for practical purposes.<br />Within this thesis exact and heuristic methods for the minimum label spanning tree problem and some variations are investigated. Regarding heuristic methods primary focus is given to the application of an ant colony optimization algorithm, which has not yet been considered for this problem. Furthermore 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. Furthermore it is shown how odd-hole inequalities can be used to cut-off fractional label solutions in order to tighten the linear programming relaxation. Results of comprehensive computational experiments are presented in order to compare the new methods to existing ones and show their superiority.<br />The last part of the 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 is to compress fingerprint minutiae templates to be able to embed this data into passport images by watermarking techniques as an additional security feature. Solutions are obtained by either metaheuristics like a memetic algorithm or greedy randomized adaptive search procedures or exact methods like branch-and-cut or branch-and-cut-and-price. Again, computational experiments show the aptitude of the proposed approach regarding the considered application.