G. Raidl, B. Hu, M. Leitner:

"Combining Variable Neighborhood Search with Integer Linear Programming for the Generalized Minimum Spanning Tree Problem";

Talk: 19th International Symposium on Mathematical Programming, Rio de Janeiro, Brasilien; 2006-07-30 - 2006-08-04.

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.

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