The Heuristic Algorithm For The Generalized Minimum Spanning Tree Problem

The Generalized Minimum Spanning Tree (GMST) problem has attracted much attention during the last few years. Its definition is that select one and only one node from each cluster to construct the minimum spanning tree (MST), the aim of it is that make the cost of this MST minimum. It is widely used in telecommunication, design of backbones in large communication networks, energy distribution, and agricultural irrigation. Since GMST was shown to be a NP-hard problem, there is no algorithm to get highquality solutions in polynomial time. Therefore many heuristic algorithms have been proposed to solve the GMST instances. Motivated by the effectiveness and efficiency of the muscle (the union of all optimal solutions) for solving other NP-hard problems, we investigate how to incorporate the muscle into heuristics design for GMST. Firstly, before define the muscle of the GMST, we show that the muscle can be well approximated by the principle and subordinate candidate sets, which can be calculated on a reduced version of GMST. Therefore, a Dynamic cAndidate set based Search Algorithm (DASA) is presented in this paper for GMST based on the analysis for the muscle to GMST. In contrast to existing heuristics, DASA employs those candidate sets to initialize and optimize solutions. During the search process, those candidate sets are dynamically adjusted to include in new features provided by good solutions. Since those candidate sets cover almost all optimal solutions, the search space of DASA can be dramatically reduced so that elite solutions can be easily found in a short time. Furthermore, a FANT algorithm based on the local search of the DASA, is presented to solve the GMST problem. It also uses the candidate sets to initialize and optimize the solutions of the GMST, and employs the local search of DASA as its local search operator. Extensive experiments demonstrate that the new algorithms including the DASA and FANT for GMST outperforms existing heuristic algorithms in terms of solution quality. And the results on the extension instances which are newly larger created, FANT algorithm outperforms the DASA.