Subgradient optimization based Lagrangian relaxation and relax-and-cut approaches for the bounded-diameter minimum spanning tree problem

Abstract

Das Problem des minimalen Spannbaums mit beschränktem Durchmesser (BDMST) ist ein schweres kombinatorisches Optimierungsproblem mit Anwendungen in der Netzwerkplanung. In der vorliegenden Diplomarbeit präsentiere ich zwei Lagrange Relaxierungsansätze für das BDMST Problem mit geradem Durchmesser, um untere Schranken und heuristische Lösungen zu finden. Der erste Lagrange Relaxierungsansatz basiert auf dem sogenannten Predecessor-Depth Modell.<br />In diesem Modell wird eine Lösung mittels Predecessor Variablen und Depth Variablen formuliert. Die relaxierten Nebenbedingungen können explizit aufgelistet werden. Um das Lagrange duale Problem zu lösen, wird das Subgradientenverfahren eingesetzt. Der zweite Lagrange Relaxierungsansatz basiert auf dem sogenannten Predecessor-Jump Modell.<br />In diesem Modell wird eine Lösung mittels Predecessor Variablen und Jump Nebenbedingungen formuliert. Da es exponentiell viele Jump-Nebenbedingungen gibt, können sie nicht explizit aufgelistet werden sondern werden dynamisch separiert. Zwei verschiedene Strategien zur Separierung von Jump-Nebenbedingungen werden präsentiert. Um das Lagrange duale Problem zu lösen wird ein Relax-and-Cut Ansatz entwickelt und das Subgradientenverfahren eingesetzt.<br />Die entwickelten Ansätze wurden mit, aus der Literatur bekannten, Instanzen getestet. Der auf dem Predecessor-Jump Modell basierende Lagrange Relaxierungsansatz liefert signifikant bessere untere Schranken verglichen mit dem Lagrange Relaxierungsansatz, der auf dem Predecessor-Depth Modell basiert. Weiters vergleiche ich die berechneten unteren Schranken mit Ergebnissen aus Gruber 2006. Die unteren Schranken, die mittels des Predecessor-Jump Modells erzielt wurden, sind mit einer Ausnahme immer besser als die LP Relaxierungswerte mit diversen Cuts aus Gruber 2006, brauchen allerdings deutlich mehr Berechnungszeit. Für zwei dieser Instanzen wird der optimale Zielfunktionswert erreicht.<br />

The Bounded-Diameter Minimum Spanning Tree (BDMST) problem is a hard combinatorial optimization problem with applications in network design. In this thesis, I present two Lagrangian relaxation approaches for the BDMST problem with even diameter bound in order to obtain lower bounds as well as heuristic solutions. The first Lagrangian relaxation approach is based on the so called Predecessor-Depth model. In this model a solution is formulated by predecessor variables and depth variables. The relaxed constraints of this model can be listed explicitly. To solve the Lagrangian duals, Subgradient Optimization is employed. The second Lagrangian relaxation approach is based on the so called Predecessor-Jump model. In this model a solution is formulated by predecessor variables and jump constraints. There are exponentially many relaxed constraints in this model. Therefore they cannot be listed explicitly but are separated dynamically.<br />Two different strategies to separate jump constraints are presented. To solve the Lagrangian duals a Relax-and-Cut approach is developed and Subgradient Optimization is employed.<br />A set of benchmark instances used in the literature serve as input for computational experiments. The Lagrangian relaxation approach based on the Predecessor-Jump model produces significantly better lower bounds than the approach based on the Predecessor-Depth model. Subsequently, I compare the computed lower bounds to results from Gruber 2006. The lower bounds produced with the Lagrangian relaxation approach on the Predecessor-Jump model are, with one exception, always better than the values of the LP relaxation with cuts from Gruber 2006 but require substantially more time to compute. For two of the instances the optimal objective value is reached.