Abstract
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 is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dror, M., Haouari, M., Chaouachi, J.S.: Generalized spanning trees. Eur. J. Oper. Res. 120, 583–592 (2000)
Duin, C.W., Volgenant, A., Voss, S.: Solving group Steiner problems as Steiner problems. Eur. J. Oper. Res. 154(1), 323–329 (2004)
Feremans, C.: Generalized spanning trees and extensions. Ph.D. thesis, Universite Libre de Bruxelles (2001)
Feremans, C., Grigoriev, A.: An approximation scheme for the generalized geometric minimum spanning tree problem with grid clustering. Technical Report NEP-ALL-2004-09-30, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (2004)
Feremans, C., Labbe, M., Laporte, G.: A comparative analysis of several formulations for the generalized minimum spanning tree problem. Networks 39(1), 29–34 (2002)
Feremans, C., Labbe, M., Laporte, G.: The generalized minimum spanning tree problem: polyhedral analysis and branch-and-cut algorithm. Networks 43(2), 71–86 (2004)
Fischetti, M., González, J.J.S., Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45, 378–394 (1997)
Ghosh, D.: Solving medium to large sized Euclidean generalized minimum spanning tree problems. Technical Report NEP-CMP-2003-09-28, Indian Institute of Management, Research and Publication Department, Ahmedabad, India (2003)
Golden, B., Raghavan, S., Stanojevic, D.: Heuristic search for the generalized minimum spanning tree problem. INFORMS J. Comput. 17(3), 290–304 (2005)
Hansen, P., Mladenovic, N.: An introduction to variable neighborhood search. In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (eds.) Meta-heuristics, Advances and Trends in Local Search Paradigms for Optimization, pp. 433–458. Kluwer Academic, Dordrecht (1999)
Hansen, P., Mladenovic, N.: A tutorial on variable neighborhood search. Technical Report G-2003-46, Les Cahiers du GERAD, HEC Montreal and GERAD, Canada (2003)
Hu, B., Leitner, M., Raidl, G.R.: Computing generalized minimum spanning trees with variable neighborhood search. In: Hansen, P., Mladenović, N., Pérez, J.A.M., Batista, B.M., Moreno-Vega, J.M. (eds.) Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, Tenerife, Spain (2005)
Ihler, E., Reich, G., Widmayer, P.: Class Steiner trees and VLSI-design. Discrete Appl. Math. 90, 173–194 (1999)
Kruskal, J.B.: On the shortest spanning subtree and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50 (1956)
Myung, Y.S., Lee, C.H., Tcha, D.W.: On the generalized minimum spanning tree problem. Networks 26, 231–241 (1995)
Pop, P.C.: The generalized minimum spanning tree problem. Ph.D. thesis, University of Twente, The Netherlands (2002)
Pop, P.C., Still, G., Kern, W.: An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size. In: Broersma, H., Johnson, M., Szeider, S. (eds.) Algorithms and Complexity in Durham 2005, Proceedings of the first ACiD Workshop, Texts in Algorithmics, vol. 4, pp. 115–121. King’s College Publications (2005)
Prim, R.C.: Shortest connection networks and some generalisations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
Reich, G., Widmayer, P.: Beyond Steiner’s problem: a VLSI oriented generalization. In: Graph-Theoretic Concepts in Computer Science WG89, pp. 196–210 (1989)
Taillard, E., Voss, S.: POPMUSIC: partial optimization metaheuristic under special intensification conditions. In: Ribeiro, C. and Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 613–629, (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the RTN ADONET under grant 504438.
Rights and permissions
About this article
Cite this article
Hu, B., Leitner, M. & Raidl, G.R. Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem. J Heuristics 14, 473–499 (2008). https://doi.org/10.1007/s10732-007-9047-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-007-9047-x