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....[ Read more ]

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.