[Back]


Contributions to Books:

M. Gruber, G. Raidl:
"(Meta-)heuristic separation of jump cuts in a branch&cut approach for the bounded diameter minimum spanning tree problem";
in: "Matheuristics - Hybridizing Metaheuristics and Mathematical Programming,volume 10 of Annals of Information Systems", Springer, 2009, ISBN: 978-1-4419-1305-0, 209 - 230.



English 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. We also introduce a new type of cuts, the center
connection cuts, to strengthen the formulation in the more difficult to
solve odd diameter case. In addition, primal heuristics are used to compute
initial solutions and to locally improve incumbent solutions identified
during Branch&Cut. 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.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_179024.pdf


Created from the Publication Database of the Vienna University of Technology.