[Back]

F. Zaubzer:
"Lagrangian relax-and-cut and hybrid methods for the bounded diameter and the hop constrained minimum spanning tree problems";
Supervisor: G. Raidl, M. Gruber; Institut für Computergraphik und Algorithmen, 2008; final examination: 2008-05.

The Bounded Diameter Minimum Spanning Tree problem (BDMST) and the
Hop Constrained Minimum Spanning Tree problems (HCMST) are NP-hard
combinatorial optimization problems which have their main application in
network design. In this thesis an existing relax-and-cut approach for nding
lower bounds and 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.
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 identi ed
and relaxed on the
y. The enhanced R&C algorithm is a so called non de-
leayed 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 initial identi cation of jump constraints with
corresponding dual variables and a generalization of jump constraints.
The metaheuristic utilized for the hybrid algorithm is an ant colony
optimization (ACO) algorithm. ACO algorithms exploit the ability of ants
nding 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.
Computational experiments have been performed on previously published
benchmark instances. The results have shown that most of the enhancements
to the R&C algorithm have lead to signi cant improvements
especially for the lower bounds compared to the original R&C algorithm.