Strong lower bounds for the prize
collecting Steiner problem in graphs
A. Lucena and M.G.C. Resende
Discrete Applied
Mathematics, vol. 141, pp. 277-294, 2004.
ABSTRACT
Given an undirected graph G with
nonnegative edges costsand nonnegative vertex penalties, the prize collecting
Steinerproblem
in graphs (PCSPG) seeks a tree of G with minimum weight.The weight of a tree is the sum of its edge
costs plus the sum ofthe penalties of those vertices not spanned by the tree.In thispaper, we present an integer programming formulation of the
PCSPGand
describe an algorithm to obtain lower bounds for the problem.The algorithm is based on polyhedral cutting
planes and is initiatedwith tests that attempt to reduce the size of the input
graph.Computational
experiments were carried out to evaluate the strengthof the formulation through its linear
programming relaxation.The algorithm found optimal solutions for 99 out of the 114instances tested.On 96
instances, integer solutions were found(thus generating optimal PCSPG solutions).On all but seveninstances, lower bounds were equal to best known upper
bounds (thusproving
optimality of the upper bounds).Of these seven
instances,four
lower bounds were off by 1 of the best known upper bound.Nine new best known upper bounds were
produced for the test set.
PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 17 June 2004
Copyright Notice