A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

• DOI: http://doi.org/10.1111/itor.12725
• Published date: 01 May 2020
• Date: 01 May 2020
• Author: Ruslán G. Marzo,Celso C. Ribeiro

Intl. Trans. in Op. Res. 27 (2020) 1419–1446

DOI: 10.1111/itor.12725

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A GRASP with path-relinking and restarts heuristic for the

prize-collecting generalized minimum spanning tree problem

Rus l ´

an G. Marzo and Celso C. Ribeiro,∗

Institute of Computing, Universidade FederalFluminense, Niter ´

oi, RJ 24210-346, Brazil

E-mail: ruslangm@id.uff.br [Marzo]; celso@ic.uff.br[Ribeiro]

Received 20 December 2018; receivedin revised form 30 August 2019; accepted 6 September 2019

Abstract

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges,

and nonnegative prizes associated to its vertices, the prize-collecting generalized minimum spanning tree

problem consists in finding a subtree of this graph thatspans exactly one vertex of each group and minimizes

the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization

of the NP-hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy

randomized adaptive search procedure) heuristic for its approximate solution, incorporating path-relinking

for search intensification and a restart strategy for search diversification. The hybridization of the GRASP

with path-relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP

iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust.

The computational experiments show that the heuristic developedin this work found very good solutions for

test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are

made available from Mendeley Data.

Keywords: prize-collecting generalized minimum spanning tree problem; generalized minimum spanning tree problem;

GRASP; metaheuristics; randomized metaheuristics; path-relinking; restarts; time-to-target plots

1. Introduction

Let G=(V,E)be a graph defined by its vertex set V={1,...,n}and its edge set E⊆V×V,

with a prize pi≥0 associated to each vertex i∈Vand a cost ce≥0 associated to each edge

e=(i,j)∈E, with i,j∈V. Without loss of generality, we assume that graph Gis complete. We

also assume that the node set Vcan be partitioned into Kdisjoint sets or groups V1,...,VK,that

is, K

k=1Vk=Vand Vk∩V=∅,foranyk, ∈{1,...,K}:k= .Lete=(i,j)∈Ebe an edge

with extremities i∈Vkand j∈V.Ifk= ,theneis said to be an intergroup edge, otherwise e

is said to be an intragroup edge. The prize-collecting generalized minimum spanning tree problem

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

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

USA.

1420 R.G. Marzo and C.C.Ribeiro / Intl. Trans. in Op. Res. 27 (2020) 1419–1446

(PC-GMSTP) consists in finding a subtree of Gspanning exactlyone vertex of each group V1,...,VK

and minimizing the total cost of the edges in the tree less the prizes of the vertices selected in each

group (Pop, 2004, 2007; Golden et al., 2008).

According to (Pop, 2007; Golden et al., 2008), the PC-GMSTP was introduced by Stanojevic

et al. (2004) in the context of the design of regional communication networks connecting local area

networks (LAN). In this application, one unique gateway needs to be identified within each LAN,

and the gateways have to be connected via a minimum spanning tree. Additionally, nodes within

the same cluster are competing to be selected as gateway nodes, and each node offers a certain

compensation (or prize) if it is selected. The problem consists in minimizing the total cost of the

links used to connect the regional networks, discounting the prizes collected at the sites selected

as the gateway locations. In the design of undersea cable networks connecting different continents

(Golden et al., 2008), not all countries or cities along the way can be directly connected to the

network, due to the high connection costs. Consequently, the designers of these undersea cable

networks usually choose one location from each of the specified set of regions that the network

traverses. Given the potential monetary benefits associated with being a location that is directly

connected to a transcontinental fiber-optic network with significant economic benefits, it is not

uncommon for cities or countries to compete against each other for selection as a location, offering

monetary incentives in the form of tax credits and rebates to the builder or operator of the network.

There are similar applications in marketing (Pop, 2007) and other areas.

If all prizes are equal to zero (or, if all prizes are simply equal for the vertices in each group of

the vertex partition), then PC-GMSTP can be reduced to the generalized minimum spanning tree

problem (GMSTP) (Feremans et al., 2004; Pop, 2004; Golden et al., 2005; Contreras-Bolton et al.,

2016). Since the decision version of the latter was proved to be NP-hard in Myung et al. (1995),

then PC-GMSTP is also NP-hard (Golden et al., 2008).

There are several integer programming formulationsfor PC-GMSTP, see,for example, Pop (2007)

and Golden et al. (2008). The formulation below is based on the generalized subtour elimination

formulation introduced by Myung et al. (1995) for GMSTP. Let zi=1ifvertexi∈Vis selected

as a group representative vertex, zi=0 otherwise. In addition, let xe=1ifedgeebelongs to the

generalized minimum spanning tree, xe=0 otherwise. A feasible solution for PC-GMSTP is any

acyclic subgraph of Gwith K−1 edges thatspans exactly one vertex of each group.The optimization

problem can be formulated as follows:

(PC-GMSTP) min 

e∈E

cexe−

i∈V

pizi(1)

subject to



i∈Vk

zi=1∀k=1,...,K(2)



e∈E(S)

xe≤

i∈S\{j}

zi∀j∈S,∀S⊂V:2≤|S|≤|V|−1(3)



e∈E

xe=K−1(4)

xe,zi∈{0,1}∀e∈E,∀i∈V.(5)

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies