Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem

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 Variable Neighborhood Search (VNS) approach which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search 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. For the third neighborhood type we apply Mixed Integer Programming to optimize local parts within candidate solution trees. 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. This work is supported by the RTN ADONET under grant 504438.