Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

Rk. Ahuja et al., Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem, MATH PROGR, 91(1), 2001, pp. 71-97
Citations number
Categorie Soggetti
Journal title
ISSN journal
0025-5610 → ACNP
Year of publication
71 - 97
SICI code
The capacitated minimum spanning tree (CMST) problem is to find a minimum c ost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The CMST problem is an NP-comp lete problem. and existing exact algorithms can solve only small size probl ems. Currently, the best available heuristic procedures for the CMST proble m are tabu search algorithms due to Amberg et al. and Sharaiha et al. These algorithms use two-exchange neighborhood structures that are based on exch anging a single node or a set of nodes between two subtrees. In this paper. we generalize their neighborhood structures to allow exchanges of nodes am ong multiple subtrees simultaneously we refer to such neighborhood structur es as multi-exchange neighborhood structures. Our first multi-exchange neig hborhood structure allows exchanges of single nodes among several subtrees. Our second multi-exchange neighborhood structure allows exchanges that inv olve multiple subtrees. The size of each of these neighborhood structures g rows exponentially with the problem size without any substantial increase i n the computational times needed to find improved neighbors. Our approach, which is based on the cyclic transfer neighborhood structure due to Thompso n and Psaraftis and Thompson and Orlin transforms a profitable exchange int o a negative cost subset-disjoint cycle in a graph. called an improvement g raph. and identifies these cycles using variants of shortest path label-cor recting algorithms. Our computational results with GRASP and tabu search al gorithms based on these neighborhood structures reveal that (i) for the uni t demand case our algorithms obtained the best available solutions for all benchmark instances and improved some: and (ii) for the heterogeneous deman d case our algorithms improved the best available solutions for most of the benchmark instances with improvements by as much as 18%. The running times our multi-exchange neighborhood search algorithms are comparable to those taken by two-exchange neighborhood search algorithms.