## A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

A.S. da Cunha, A. Lucena, N. Maculan, and M.G.C. Resende

Published online in Discrete Applied Mathematics, 2008, doi:10.1016/j.dam.2008.02.014.

**ABSTRACT**

Given an undirected graph G with penalties associated with its vertices
and costs associated with its edges, a Prize Collecting Steiner (PCS)
tree is either an isolated vertex of G or else any tree of G, be it
spanning or not. The weight of a PCS tree equals the sum of the costs
for its edges plus the sum of the penalties for the vertices of G not
spanned by the PCS tree. Accordingly, the Prize Collecting Steiner
Problem in Graphs (PCSPG) is to find a PCS tree with the lowest weight.
In this paper, after reformulating and reinterpreting a given PCSPG
formulation, we use a Lagrangian Non Delayed Relax and Cut (NDRC)
algorithm to generate primal and dual bounds to the problem. The
algorithm was capable of adequately dealing with the exponentially many
candidate inequalities to dualize. It incorporates ingredients such as
a new PCSPG reduction test, an effective Lagrangian heuristic and a
modification in the NDRC framework that allowed duality gaps to be
further reduced. The Lagrangian heuristic suggested here dominates
their PCSPG counterparts in the literature. The NDRC PCSPG lower
bounds, most of the time, nearly matched corresponding Linear
Programming relaxation bounds.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified:* 12 June
2008*

Copyright Notice