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.

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.

http://publik.tuwien.ac.at/files/PubDat_179024.pdf

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