An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search

• Published date: 01 May 2021
• Author: Carlos Contreras‐Bolton,Víctor Parada
• Date: 01 May 2021
• DOI: http://doi.org/10.1111/itor.12880

Intl. Trans. in Op. Res. 28 (2021) 1190–1212

DOI: 10.1111/itor.12880

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An effective two-level solution approach for the

prize-collecting generalized minimum spanning tree

problem by iterated local search

Carlos Contreras-Boltonaand Víctor Paradab,c, ∗

aDepartamento de Ingeniería Industrial, Universidad de Concepción, Concepción 4070409, Chile

bDepartamento de Ingeniería Informática, Universidadde Santiago de Chile, Santiago 9170124, Chile

cInstituto Sistemas Complejos de Ingeniería (ISCI), Santiago 8370397, Chile

E-mail: carlos.contreras.b@udec.cl [Contreras-Bolton]; victor.parada@usach.cl [Parada]

Received 22 January 2020; received in revised form 31 August 2020; accepted 7 September 2020

Abstract

The prize-collecting generalized minimum spanning tree problem consists of finding a minimum cost span-

ning tree in an undirected graph, considering that the vertices are divided into clusters, that there is a non-

negative 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 chal-

lenge 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 workson a two-level solution approach, taking advantageof the structure

of the problem. The first-level subproblem aims to select a vertex for each cluster, and the second-level sub-

problem addresses the determination of the minimum spanning tree covering such vertices. The performance

of the resulting algorithm is evaluated with the most challenging instances fromthe literature, comparing the

results with the state-of-the-art algorithm. The computational experiment conducted shows that, both in ex-

isting instances and in a new group of instances presented in this paper, the proposed algorithm outperforms

the state-of-the-art algorithm.

Keywords:priz e-collecting generalized minimumspanning tree problem; iterated local search; metaheuristics

1. Introduction

Identifying a minimum cost spanning tree on a graph is an optimization problem that has many

practical applications; however, in some of these problems, the determination of the optimal

∗Corresponding author.

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

C. Contreras-Bolton and V. Parada / Intl. Trans. in Op. Res. 28 (2021) 1190–1212 1191

solution is a challenging computational task. The applications arise in the design of networks,

including computer networks, telecommunications networks, transportation networks, water sup-

ply networks, and electrical grids (Graham and Hell, 1985). The simpler problem, known as the

minimum spanning tree problem (MSTP), addresses the determination of the subset of the edges

that connect all vertices without any cycle and with the minimum total weight. Complex problems

arise when the set of vertices of the graph is divided into clusters, and a minimum spanning tree

must reach only one vertex in each cluster; this problem was introduced by Myung et al. (1995),

and it is known as the generalized minimum spanning tree problem (GMSTP).

The GMSTP has three variants in the scientific literature. One variant introduced by Stano-

jevic et al. (2004) considered that each vertex of the graph has a cost or prize associated with

it, in addition to the associated costs to the edges. This problem is called the prize-collecting

generalized minimum spanning tree problem (PC-GMSTP). Another variant introduced by Ih-

ler et al. (1999) and Dror et al. (2000) that addresses the finding of a minimum spanning tree

reaching at least one vertex from each cluster is known as L-GMSTP. The third variant was

introduced by Leitner (2016) who included some additional constraints that allow for limit-

ing the communication delay of the resulting network in regional or metropolitan area net-

works, giving rise to the generalized hop-constrained minimum spanning tree problem (GHM-

STP). The three variants are known to be NP-hard (Pop, 2020), and in this paper, we focus on

PC-GMSTP.

Formally, PC-GMSTP is defined by an undirected graph with vertices divided into rclusters,

and the purpose is to determine a minimum cost spanning tree that reaches only one vertex of

each cluster. Formally, let there be an undirected graph G=(V,E), where V=1,...,nis a set

of vertices, and E=1,...,mis a set of edges, and let V1,...,Vrbe a division of Vinto rclus-

ters such that V=V1∪V2∪···∪Vrand Vi∩Vj=∅,∀i,j∈{1,...,r}and i= j. The edges are

defined only between vertices that belong to different clusters. In addition, the cost of an edge

e=(u,v)∈Eis given by ce, and the prize of a vertex vis given by pv,∀v∈Vand ce,pv∈R.When

the prizes associated with the vertices are zero or equal for all of the vertices that belong to a deter-

mined cluster, the PC-GMSTP reduces to the GMSTP. In addition, since the GMSTP is NP-hard,

as was shown in Myung et al. (1995) using a polynomial transformation of the node cover prob-

lem, the PC-GMSTP is NP-hard as well. Figure 1 illustrates a PC-GMSTP example with an undi-

rected graph of 51 vertices divided into 11 clusters and a spanning tree reaching only one vertex of

each cluster.

The PC-GMSTP can be formulated as both mixed-integer programming and as integer pro-

gramming. An efficient formulation is the 0-1 mixed-integer programming called the “local-global”

formulation, which distinguishes between global and local connections, in which the global con-

nections are the intercluster connections, and the local connections are connections among vertices

in various clusters (Pop, 2007). It is one of the more efficient formulations for a general-purpose

solver as CPLEX. This formulation is based on the notion that, for each cluster Vk,k=1,...,r,

there must be a directed global path fromVkto each other cluster Vj,j= k. Foreach k, these paths

together form a directed tree rooted at Vk. Thus, the mathematical formulation considers four vari-

ables : y,λ,x,andz,whereyis a spanning tree of the global graph, yij(i,j∈{1,...,r}), and it is

the only global variable that is forced to be integral. Hence, yij =1ifclusterViis connected to

cluster Vjand yij =0 otherwise. Let λkij =1ifclusterVjis the parent of cluster Vion a spanning

tree rooted at Vk, with k= i= jand 0 otherwise. In addition, let xe=1ifedgeebelongs to the

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies