An Effective Two-Level Solution Approach for the Prize-Collecting Generalized Minimum Spanning Tree Problem by Iterated Local Search

The prize-collecting generalized minimum spanning tree problem consists of finding a minimum cost spanning tree in an undirected graph, considering that the vertices are divided into clusters, that there is a nonnegative cost associated with each edge, that there is a prize to be collected on each vertex, and that only one vertex of each cluster belongs to the tree. Due to its NP-hardness, this problem remains a computational challenge even for small instances, and the practical applications that arise in telecommunication networks can attain large dimensions. The state-of-the-art algorithm finds good solutions for several instances; however, the quality of solutions and the computing time for large instances remain to be improved. We propose an iterated local search algorithm that works on a two-level solution approach, taking advantage of the structure of the problem. The first-level subproblem aims to select a vertex for each cluster, and the second-level subproblem addresses the determination of the minimum spanning tree covering such vertices. The performance of the resulting algorithm is evaluated with the most challenging instances from the literature, comparing the results with the state-of-the-art algorithm. The computational experiment conducted shows that, both in existing instances and in a new group of instances presented in this paper, the proposed algorithm outperforms the state-of-the-art algorithm. © 2020 The Authors. International Transactions in Operational Research © 2020 International Federation of Operational Research Societies