[Zurück]

G. Raidl, B. Hu, M. Leitner:
"Combining Variable Neighborhood Search with Integer Linear Programming for the Generalized Minimum Spanning Tree Problem";
Vortrag: 19th International Symposium on Mathematical Programming, Rio de Janeiro, Brasilien; 30.07.2006 - 04.08.2006.

We consider the generalized version of
the classical Minimum Spanning Tree
problem where the nodes of a graph
are partitioned into clusters and exactly
one node from each cluster must be
connected. We present a general Variable
Neighborhood Search (VNS) approach
which uses three different neighborhood
types. Two of them work in
complementary ways in order to maximize
the effectivity. Both are large in
the sense that they contain exponentially
many candidate solutions, but efficient
polynomial-time algorithms are used to
identify best neighbors. The third neighborhood
type uses Integer Linear Programming
to solve parts of the problem
to provable optimality. Tests on Euclidean
and random instances with up
to 1280 nodes indicate especially on instances
with many nodes per cluster significant
advantages over previously published
metaheuristic approaches.