[Back]

P. Putz:
"Subgradient optimization based lagrangian relaxation and relax-and-cut approaches for the bounded-diameter minimum spanning tree problem";
Supervisor: G. Raidl, M. Gruber; Institut für Computergraphik und Algorithmen, 2007; final examination: 2007-10.

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 rst 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. 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.
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 signi cantly 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.