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.
ABSTRACT
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