Paper Info
Title
Heuristic Search for the Generalized Minimum Spanning Tree Problem
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.
Year
DOI
Venue
2005
10.1287/ijoc.1040.0077
INFORMS Journal on Computing
Keywords
Field
DocType
generalized minimum spanning tree,optimal solution,local-search heuristic,tsplib set,genetic-algorithm procedure,computational test,high-quality solution,computational experiment,heuristic search approach,gmst problem,heuristic search,test problem,heuristics,networks,minimum spanning tree,genetic algorithms,tree algorithms,local search
Approximation algorithm,Heuristic,Incremental heuristic search,Mathematical optimization,Tree traversal,Heuristics,Spanning tree,Local search (optimization),Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
17
3
1091-9856
Citations 
PageRank 
References 
18
1.07
8
Authors
3
Name
Order
Citations
PageRank
Bruce L. Golden11110176.17
S. Raghavan221616.30
Daliborka Stanojević3292.52