Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/4994

Generalized minimum spanning tree problem

Authors Che, Chan Hou
Issue Date 2006
Summary The Generalized Minimum Spanning Tree problem denoted by GMST is a generalized combinatorial optimization problem, spanning exactly one node from each cluster in an undirected graph. GMST problems are encountered in telecom-munications network planning. In our thesis, we developed a meta-heuristic method, Tabu Search algorithm, to solve this problem. A new heuristic relaxation algorithm based on this Tabu Search to estimate the lower bound is also proposed. We compared computational results of different methods, including a mixed integer programming model, Tabu Search and Genetics Algorithm. In our computational tests on 194 TSPLIB in-stances, Tabu Search found all optimal solutions (the optimal solutions are known in 152 instances out of the 194 TSP instances). For those 42 unsolved instances, our algorithm improved some previously best known solutions. Moreover, lower bounds of some unknown problems are also improved by our heuristic relaxation algorithm.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2006
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 339 B HTML