Lagrangian relax-and-cut and hybrid methods for the bounded diameter and the hop constrained minimum spanning tree problems

Abstract

Das minimale Spannbaumproblem mit einer Beschränkung des Durchmessers (Bounded Diameter Minimum Spanning Tree -- BDMST) ist ein NP schweres kombinatorisches Optimierungsproblem aus dem Bereich des Netzwerkdesigns. Ein verwandtes Problem ist das minimale Spannbaum Problem mit festgesetztem Wurzelknoten und einer beschränkten Anzahl von Kanten zwischen dem Wurzelknoten und jedem Blattknoten (Hop Constrained Minimum Spanning Tree -- HCMST). In dieser Arbeit wird ein bestehender Relax-and-Cut (R&C) Algorithmus zur approximativen Lösung dieser Probleme verbessert und erweitert und ein hybrider Algorithmus basierend auf dem R&C Algorithmus und einer Metaheuristik vorgestellt.<br />Der R&C Algorithmus basiert auf einer integer linear programming (ILP) Formulierung mit einer exponentiellen Anzahl von linearen Bedingungen, den sogenannten Jump-Constraints. Dabei werden nicht erfüllte Bedingungen während der Laufzeit des Optimierungsalgorithmus identifiziert und relaxiert. Verbessert wurde der R&C Algorithmus durch eine aufwändige Verwaltung der identifizierten linearen Bedingungen und durch den Einsatz eines non delayed R&C Verfahrens. Die entwickelten Erweiterungen sind der Einsatz von generalisierten Jump-Constraints und eine initiale Erzeugung einer Menge von Jump-Constraints mit zugehörigen dualen Variablen.<br />Die für den hybriden Algorithmus verwendete Metaheuristik ist eine Ameisenkolonie Optimierung (ACO).<br />ACO Algorithmen nutzen die Fähigkeit von Ameisen kurze Wege zwischen Nahrungsquellen und ihrem Nest durch das Hinterlassen von Pheromonen am Weg zu finden. Die Funktionsweise entspricht einem positiv rückgekoppelten System. Der hybride Algorithmus verbindet die Pheromoninformationen mit Informationen vom R&C Algorithmus, sodass zur Lösungsfindung neben Pheromonwerten zusätzliche heuristische Werte einfließen. Experimentelle Berechnungen mit schon bestehenden Probleminstanzen wurden durchgeführt. Die Resultate zeigen, dass die Verbesserungen des R&C Algorithmus zu deutlich besseren Ergebnissen -- im Speziellen zu deutlich höheren unteren Schranken -- geführt haben.

The Bounded Diameter Minimum Spanning Tree problem (BDMST) and the Hop Constrained Minimum Spanning Tree problems (HCMST) are NP-hard combinatorial optimization problem which have their main application in network design. In this thesis an existing relax-and-cut approach for finding approximate solutions to those problems is enhanced and extended, and a hybrid algorithm based on the relax-and-cut approach as well as on an existing metaheuristic namely an ant colony optimization (ACO) is presented.<br />The enhanced relax-and-cut (R&C) approach is based on an integer linear programming (ILP) formulation which relies on so called jump constraints. The number of jump constraints in this formulation is exponential by means of the instance size. Therefore, violated constraints are identified and relaxed on the fly. The enhanced R&C algorithm is a so called non deleayed relax-and-cut algorithm which is based on subgradient optimization. Since the number of separated jump inequalities can be large, a sophisicated management of a pool of such constraints is used. The two main extensions to this R&C approach are the efficient identification of violated jump constraints based on dual variables and a generalization of jump constraints.<br />The metaheuristic utilized for the hybrid algorithm is an Ant Colony Optimization (ACO) algorithm. ACO algorithms exploit the ability of ants finding short paths between their nest and food sources by depositing pheromone. This works as a positive feedback system. The concept of the hybrid algorithm is the utilization of information obtained by the relax-and-cut approach as a heuristic component in the ACO algorithm that is mixed with the pheromone information of the ACO algorithm.<br />Computational results have been produced with previously published instances. The results have shown that the large number of enhancements to the R&C algorithm has lead to significant improvements especially for the lower bounds compared to the original R&C algorithm.