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

Blum, Christian; Blesa, Maria J.

Comput. Oper. Res. 32, No. 6, 1355-1377 (2004).

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.

MSC:

90C59	Approximation methods and heuristics in mathematical programming
90C27	Combinatorial optimization

Keywords:

\(k\)-cardinality tree problem; Metaheuristics; Combinatorial optimization; Ant Colony Optimization; Evolutionary computation; Tabu search; Spanning trees

Software:

HC-ACO; Tabu search; K_TREE/K_SUBGRAPH

References:

[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
[5]	Philpott, A. B.; Wormald, N. C., On the optimal extraction of ore from an open-cast mine (1997), University of Auckland: University of Auckland New Zealand
[7]	Borndörfer, R.; Ferreira, C.; Martin, A., Decomposing matrices into blocks, SIAM Journal on Optimization, 9, 1, 236-269 (1998) · Zbl 1032.90523
[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
[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)
[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)
[24]	Blum, C., Ant colony optimization for the edge-weighted \(k\)-cardinality tree problem, (Langdon, W. B.; Cantú-Paz, E.; Mathias, K.; Roy, R.; Davis, D.; Poli, R.; Balakrishnan, K.; Honavar, V.; Rudolph, G.; Wegener, J.; Bull, L.; Potter, M. A.; Schultz, A. C.; Miller, J. F.; Burke, E.; Jonoska, N., Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002) (2002), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo, CA), 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
[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: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[29]	Bäck, T., Evolutionary algorithms in theory and practice (1996), Oxford University Press: 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
[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)
[38]	Beasley, J. E., OR-librarydistributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990)