Groupe d’études et de recherche en analyse des décisions

G-2004-23

Variable Neighborhood Search for the Vertex Weighted k-Cardinality Tree

, et

This paper presents some new heuristics based on variable neighborhood search to solve the vertex weighted k-cardinality tree problem. An efficient local search procedure is also developed for use within these heuristics. Our computational results demonstrate that the new heuristics substantially outperform the state-of-the-art methodologies, including a Tabu search and genetic algorithm recently proposed in the literature. We also show that a decomposition approach is best for larger problem sizes than previously investigated. Thus, our findings advance in a significant way the capacity to solve this important class of problems.

, 16 pages