Abstract
Research efforts in metaheuristics have shown that an intelligent incorporation of more classical optimization techniques in metaheuristics can be very beneficial. In this paper, we combine the metaheuristic ant colony optimization with dynamic programming for the application to the NP – hard k-cardinality tree problem. Given an undirected graph G with node and/or edge weights, the problem consists of finding a tree in G with exactly k edges such that the sum of the weights is minimal. In a standard ant colony optimization algorithm, ants construct trees with exactly k edges. In our algorithm, ants may construct trees that have more than k edges, in which case we use a recent dynamic programming algorithm to find—in polynomial time—the best k-cardinality tree embedded in the bigger tree constructed by the ants. We show that our hybrid algorithm improves over the standard ant colony optimization algorithm and, for node-weighted grid graph instances, is a current state-of-the-art method.
This work was supported by the Spanish CICYT project no. TIC-2002-04498-C05-03 (TRACER), and by the “Juan de la Cierva” program of the Spanish Ministry of Science and Technology of which Christian Blum is a post-doctoral research fellow.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blesa, M., Moscato, P., Xhafa, F.: A memetic algorithm for the minimum weighted k-cardinality tree subgraph problem. In: Proc. of the 4th Metah. Intern. Conf., vol. 1, pp. 85–90 (2001)
Blesa, M., 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, pp. 648–652 (2000)
Blum, C.: Revisiting dynamic programming for finding optimal subtrees in trees. Tech. Rep. LSI-04-57, Universitat Politècnica Catalunya, Spain (2004) (submitted)
Blum, C., Blesa, M.: New metaheuristic approaches for the edge-weighted k-cardinality tree problem. Computers & Operations Research 32, 1355–1377 (2005)
Blum, C., Ehrgott, M.: Local search algorithms for the k-cardinality tree problem. Discr. Appl. Math. 128, 511–540 (2003)
Brimberg, J., Urošević, D., Mladenović, N.: Variable neighborhood search for the vertex weighted k-cardinality tree problem. Eur. J. of Op. Res. (2005) (in press)
Bui, T.N., Sundarraj, G.: Ant system for the k-cardinality tree problem. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 36–47. Springer, Heidelberg (2004)
Cheung, S.Y., Kumar, A.: Efficient quorumcast routing algorithms. In: Proceedings of INFOCOM 1994. IEEE Society Press, Los Alamitos (1994)
Dorigo, M.: Optimization, Learning and Natural Algorithms (in Italian). PhD, Dipartimento di Elettronica, Politecnico di Milano, Italy (1992)
Dorigo, M., Maniezzo, V., Colorni, A.: Ant System: Optimization by a colony of cooperating agents. IEEE TSMC – Part B 26, 29–41 (1996)
Ehrgott, M., Freitag, J.: K_TREE / K_SUBGRAPH: A program package for minimal weighted k-cardinality-trees and -subgraphs. Eur. J. of. Op. Res. 1, 214–225 (1996)
Ehrgott, M., Freitag, J., Hamacher, H.W., Maffioli, F.: Heuristics for the k-cardinality tree and subgraph problem. Asia-Pac. J. of Op. Res. 14, 87–114 (1997)
Fischetti, M., Hamacher, H.W., Jørnsten, K., Maffioli, F.: Weighted k-cardinality trees: Complexity and polyhedral structure. Networks 24, 11–21 (1994)
Freitag, J.: Minimal k-cardinality trees (in German). Master’s thesis, Department of Mathematics, University of Kaiserslautern, Germany (1993)
Jörnsten, K., Løkketangen, A.: Tabu search for weighted k-cardinality trees. Asia-Pac. J. of Op. Res 14, 9–26 (1997)
Maffioli, F.: Finding a best subtree of a tree. Tech. Rep. 91.041, Politecnico di Milano, Dipartimento di Elettronica, Italy (1991)
Uehara, R.: The number of connected components in graphs and its applications. IEICE Tech. Rep. COMP99-10, Komazawa University, Japan (1999)
Urošević, D., Brimberg, J., Mladenović, N.: Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem. Comp. & Op. Res. 31, 1205–1213 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blum, C., Blesa, M. (2005). Combining Ant Colony Optimization with Dynamic Programming for Solving the k-Cardinality Tree Problem. In: Cabestany, J., Prieto, A., Sandoval, F. (eds) Computational Intelligence and Bioinspired Systems. IWANN 2005. Lecture Notes in Computer Science, vol 3512. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494669_4
Download citation
DOI: https://doi.org/10.1007/11494669_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26208-4
Online ISBN: 978-3-540-32106-4
eBook Packages: Computer ScienceComputer Science (R0)