ALCOMFT-TR-03-37

C. Blum and M. Blesa
New Metaheuristic Approaches for the Edge-Weighted k-Cardinality Tree Problem
Barcelona. Work packages 3, 4 and 5. September 2003.

Abstract: In this paper we deal with metaheuristics for the k-cardinality tree (KCT) problem, a combinatorial optimization problem which generalizes the well known minimum-weight spanning tree problem. Given a node-weighted or edge-weighted graph G=(V,E), it consists in finding a tree in G with exactly k<= |V|-1 edges, such that the sum of the weights is minimal. This problem has several applications in many different areas.

We propose three different metaheuristic approaches to tackle this problem: A Tabu Search approach, an Evolutionary Computation approach and, and Ant Colony Optimization approach. All these approaches have been based on the same solution neighborhood structure. Although some metaheuristic approaches can be found in the literature, there is a lack of benchmark problem instances and therefore also a lack of valuable comparisons between these approaches. We also propose a benchmark set for the KCT problem characterized by several distinguishing features. Our results show that these heterogeneity on the considered graphs leads to different behaviors of the algorithms. No metaheuristic can be identified as the best approach when solving the problem on them. It is rather the case that each approach has its advantages for certain types of graphs and, in general, for certain areas of the problem instance space.

Keywords: k-Cardinality Tree Problem, Metaheuristics, Combinatorial Optimization, Ant Colony Optimization, Evolutionary Computation, Tabu Search, Spanning Trees

Postscript file: ALCOMFT-TR-03-37.ps.gz (246 kb).