(Meta-)Heuristic Separation of Jump Cuts for the Bounded Diameter
Minimum Spanning Tree Problem

Martin Gruber and Guenther R. Raidl

Institute of Computer Graphics and Algorithms
Vienna University of Technology, Vienna, Austria
{gruber|raidl}@ads.tuwien.ac.at,

Abstract. The bounded diameter minimum spanning tree problem is
an NP-hard combinatorial optimization problem arising, for example, in
network design when quality of service is of concern. We solve a strong
integer linear programming formulation based on so-called jump inequalities
by a Branch&Cut algorithm. As the separation subproblem of identifying
currently violated jump inequalities is difficult, we approach it
heuristically by two alternative construction heuristics, local search, and
optionally tabu search. The overall algorithm performs excellently, and
we were able to obtain proven optimal solutions for some test instances
that were too large to be solved so far.