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 in Proceeding of Mathematical Programming in Rio, pp. 72-78, Búzios, Rio de Janeiro, Brazil, 2003.


In this paper, we address the problem of finding a minimal weight tree in an undirected graph with non-negative edge costs and non-negative vertex penalties, the Prize Collecting Steiner Problem in Graphs (PCSPG).  Using an approach proposed by Beasley (1989), we formulate the PCSPG as a restricted minimum forest problem, which is amenable to be solved by a Lagrangian relaxation procedure.  In our approach, some inequalities are dualized when they first become violated and are dropped when their multipliers are zero.  As soon as new stringer lower bounds are found, we temporarily modify the cost of the edges present at the Lagrangean solution, and call an upper bounding procedure based on an approximation algorithm (Minkoff, 2000).  We report several computational results.

PDF file of paper

DjVu file of paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 19 December 2003

Copyright Notice