Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Bei dem Entwurf von metaheuristischen Optimierungsmethoden besteht ein Zielkonflikt zwischen Anwendungsbreite und Effektivität. Für große anwendungsnahe Instanzen von kombinatorischen Optimierungsproblemen funktionieren Standard-Metaheuristiken für gewöhnlich nicht besonders gut. Um bessere Ergebnisse zu erzielen muss die Optimierungsmethode an das zu optimierende Problem angepasst werden. Wissen über die Struktur guter Lösungen kann genutzt werden indem ein sogenannter Bias in den Komponenten der Metaheuristik integriert wird. Diese problemspezifischen Anpassungen erlauben es die Leistungsfähigkeit zu steigern. In dieser Arbeit werden die Charakteristika von qualitativ hochwertigen Lösungen dreier Spannbaumproblemen mit unterschiedlichen Nebenbedingungen untersucht: das Optimal Communication Spanning Tree Problem, das Quadratic Minimum Spanning Tree Problem und das Bounded Diameter Minimum Spanning Tree Problem. Verschiedene relevante Eigenschaften von Spannbäumen werden identifiziert, welche untersucht werden sollten wenn ein Spannbaumproblem analysiert wird. Basierend auf den gewonnenen Erkenntnissen bezüglich der Struktur qualitativ hochwertiger Lösungen, werden effiziente und robuste Lösungsverfahren für jedes der Probleme entwickelt. Experimentelle Studien analysieren die Leistungsfähigkeit der entwickelten Ansätze im Vergleich zu den bisher erfolgreichsten Verfahren.