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.


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