Solving the generalized minimum spanning tree problem with simulated annealing

We consider a generalization of the minimum spanning tree problem, called the generalized minimum spanning tree problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present an effective algorithm for this problem. The method combines a simulated annealing algorithm (SA) with a local greedy algorithm. The heuristic that we proposed found solutions that were optimal for graphs with nodes up to 280 and were within at most 24% of optimality for larger problems, while the existing algorithms from the literature become computationally intractable.