New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem. (English) Zbl 1107.90044

Summary: We propose three metaheuristic approaches, namely a tabu search, an evolutionary computation and an ant colony optimization approach, for the edge-weighted \(k\)-cardinality tree (KCT) problem. This problem is an \(NP\)-hard combinatorial optimization problem that generalizes the well-known minimum weight spanning tree problem. Given an edge-weighted graph \(G=(V,E)\), it consists of finding a tree in \(G\) with exactly \(k\leq |V|-1\) edges, such that the sum of the weights is minimal. First, we show that our new metaheuristic approaches are competitive by applying them to a set of existing benchmark instances and comparing the results to two different tabu search methods from the literature. The results show that these benchmark instances are not challenging enough for our metaheuristics. Therefore, we propose a diverse set of benchmark instances that are characterized by different features such as density and variance in vertex degree. We show that the performance of our metaheuristics depends on the characteristics of the tackled instance, as well as on the cardinality. For example, for low cardinalities the ant colony optimization approach is best, whereas for high cardinalities the tabu search approach has advantages.


90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
Full Text: DOI


[1] Hamacher HW, Jörnsten K, Maffioli F. Weighted k-cardinality trees. Technical Report 91.023, Politecnico di Milano, Dipartimento di Elettronica, Italy, 1991.
[2] Hamacher HW, Jörnsten K. Optimal relinquishment according to the Norwegian petrol law: a combinatorial optimization approach. Technical Report No. 7/93, Norwegian School of Economics and Business Administration, Bergen, Norway, 1993.
[3] Foulds, L.R.; Hamacher, H.W.; Wilson, J., Integer programming approaches to facilities layout models with forbidden areas, Annals of operations research, 81, 405-417, (1998) · Zbl 0906.90103
[4] Foulds LR, Hamacher HW. A new integer programming approach to (restricted) facilities layout problems allowing flexible facility shapes. Technical Report 1992-3, University of Waikato, Department of Management Science, 1992.
[5] Philpott, A.B.; Wormald, N.C., On the optimal extraction of ore from an open-cast mine, (1997), University of Auckland New Zealand
[6] Borndörfer R, Ferreira C, Martin A. Matrix decomposition by branch-and-cut. Technical Report, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1997.
[7] Borndörfer, R.; Ferreira, C.; Martin, A., Decomposing matrices into blocks, SIAM journal on optimization, 9, 1, 236-269, (1998) · Zbl 1032.90523
[8] Cheung SY, Kumar A. Efficient quorumcast routing algorithms. In: Proceedings of INFOCOM’94. Los Alamitos, USA, Silver Spring, MD: IEEE Society Press; 1994.
[9] Garg, N.; Hochbaum, D., An \(O( logk)\) approximation algorithm for the k minimum spanning tree problem in the plane, Algorithmica, 18, 1, 111-121, (1997) · Zbl 0866.68076
[10] Fischetti, M.; Hamacher, H.W.; Jörnsten, K.; Maffioli, F., Weighted k-cardinality treescomplexity and polyhedral structure, Networks, 24, 11-21, (1994) · Zbl 0809.90124
[11] Marathe, M.V.; Ravi, R.; Ravi, S.S.; Rosenkrantz, D.J.; Sundaram, R., Spanning trees short or small, SIAM journal on discrete mathematics, 9, 2, 178-200, (1996) · Zbl 0855.05058
[12] Maffioli F. Finding a best subtree of a tree. Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, Italy, 1991.
[13] A. Zelikovsky, D. Lozevanu, Minimal and bounded trees. In: Tezele Cong. XVIII Acad. Romano-Americane, Kishinev, 1993. p. 25-6.
[14] Freitag J. Minimal k-cardinality trees. Master’s thesis, Department of Mathematics, University of Kaiserslautern, Germany, 1993 [in German].
[15] Uehara R. The number of connected components in graphs and its applications. IEICE Technical Report COMP99-10, Natural Science Faculty, Komazawa University, Japan, 1999.
[16] Ehrgott, M.; Freitag, J.; Hamacher, H.W.; Maffioli, F., Heuristics for the k-cardinality tree and subgraph problem, Asia-Pacific journal of operational research, 14, 1, 87-114, (1997) · Zbl 0906.90167
[17] Ehrgott, M.; Freitag, J., K_TREE/K_subgrapha program package for minimal weighted k-cardinality-trees and -subgraphs, European journal of operational research, 1, 93, 214-225, (1996) · Zbl 0925.90368
[18] Blum, C.; Roli, A., Metaheuristics in combinatorial optimizationoverview and conceptual comparison, ACM computing surveys, 35, 3, 268-308, (2003)
[19] Blesa MJ, Moscato P, Xhafa F. A memetic algorithm for the minimum weighted k-cardinality tree subgraph problem. In: Proceedings of the Metaheuristics International Conference MIC’2001, vol. 1, Porto, Portugal, July 2001. p. 85-90.
[20] Blesa MJ, Xhafa F. A C++ implementation of tabu search for k-cardinality tree problem based on generic programming and component Reuse. In: Net.ObjectDays 2000 Tagungsband, Erfurt, Germany, 2000. p. 648-52. Net.ObjectDays-Forum.
[21] Jörnsten, K.; Løkketangen, A., Tabu search for weighted k-cardinality trees, Asia-Pacific journal of operational research, 14, 2, 9-26, (1997) · Zbl 0909.90265
[22] Løkketangen, A., Tabu search—using the search experience to guide the search process. an introduction with examples, Aicom, 8, 2, 78-85, (1995)
[23] Mladenović N, Urošević D. Variable neighborhood search for the k-cardinality tree problem. In: Proceedings of the Metaheuristics International Conference MIC’2001, vol. 2, 2001. p. 743-7.
[24] Blum, C., Ant colony optimization for the edge-weighted k-cardinality tree problem, (), 27-34
[25] Blum, C.; Ehrgott, M., Local search algorithms for the k-cardinality tree problem, Discrete applied mathematics, 128, 511-540, (2003) · Zbl 1038.90085
[26] MALLBA-Project. www.lsi.upc.es/ mallba/public/library/TabuSearch/minktree.html, 2001.
[27] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and operations research, 5, 533-549, (1986) · Zbl 0615.90083
[28] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[29] Bäck, T., Evolutionary algorithms in theory and practice, (1996), Oxford University Press New York · Zbl 0877.68060
[30] Fogel, D.B., An introduction to simulated evolutionary optimization, IEEE transactions on neural networks, 5, 1, 3-14, (1994)
[31] Hertz, A.; Kobler, D., A framework for the description of evolutionary algorithms, European journal of operational research, 126, 1-12, (2000) · Zbl 0970.90122
[32] Dorigo M. Optimization, learning and natural algorithms. Ph.D. thesis, DEI, Politecnico di Milano, Italy, 1992, 140pp [in Italian].
[33] Dorigo, M.; Di Caro, G.; Gambardella, L.M., Ant algorithms for discrete optimization, Artificial life, 5, 2, 137-172, (1999)
[34] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant systemoptimization by a colony of cooperating agents, IEEE transactions on systems, man and cybernetics—part B, 26, 1, 29-41, (1996)
[35] Dorigo, M.; Gambardella, L.M., Ant colony systema cooperative learning approach to the traveling salesman problem, IEEE transactions on evolutionary computation, 1, 1, 53-66, (1997)
[36] Stützle, T.; Hoos, H.H., \(MAX\)-\(MIN\) ant system, Future generation computer systems, 16, 8, 889-914, (2000)
[37] Blum C, Roli A, Dorigo M. HC-ACO: the hyper-cube framework for ant colony optimization. In: Proceedings of Metaheuristics International Conference MIC’2001. Porto, Portugal, July 2001. p. 399-403.
[38] Beasley, J.E., OR-librarydistributing test problems by electronic mail, Journal of the operational research society, 41, 11, 1069-1072, (1990)
[39] KCTLIB. http://iridia.ulb.ac.be/ cblum/kctlib/, 2003.
[40] Cormen T, Leisersoon C, Rivest R. Introduction to algorithms 2nd ed. Cambridge, MA: MIT Press; and New York: McGraw-Hill; 2001.
[41] Blum C, Blesa MJ. Metaheuristics for the edge-weighted k-cardinality tree problem. Technical Report TR/IRIDIA/2003-02, IRIDIA, Université Libre de Bruxelles, Belgium, 2003. Also available as technical report LSI-03-1-R, LSI, Universitat Politècnica de Catalunya, Spain.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.