Premium
An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search
Author(s) -
ContrerasBolton Carlos,
Parada Víctor
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12880
Subject(s) - spanning tree , iterated function , minimum spanning tree , vertex (graph theory) , distributed minimum spanning tree , steiner tree problem , prim's algorithm , computer science , iterated local search , mathematical optimization , enhanced data rates for gsm evolution , mathematics , k minimum spanning tree , graph , tree (set theory) , state (computer science) , algorithm , local search (optimization) , tree structure , theoretical computer science , combinatorics , artificial intelligence , k ary tree , binary tree , mathematical analysis
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.