Heuristic search for the generalized minimum spanning tree problem

Heuristic search for the generalized minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2007362
Country: United States
Volume: 17
Issue: 3
Start Page Number: 290
End Page Number: 304
Publication Date: Jun 2005
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: computers, graphs, heuristics: genetic algorithms
Abstract:

The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, and even finding a constant factor approximation algorithm is NP-hard. In this paper, we present two heuristic search approaches for the GMST problem: local search and a genetic algorithm. Our computational experiments show that these heuristics rapidly provide high-quality solutions for the GMST and outperform some previously suggested heuristics for the problem. In our computational tests on 211 test problems (including 169 problems from the TSPLIB set), our local-search heuristic found the optimal solution in 179 instances and our genetic-algorithm procedure found the optimal solution in 185 instances (out of the 211 instances, the optimal solution is known in 187 instances). Further, on each of the 19 unsolved instances from TSPLIB, both our local-search heuristic and genetic-algorithm procedure improved upon the best previously known solution.

Reviews

Required fields are marked *. Your email address will not be published.