Local search with perturbations for the prize-collecting Steiner tree problem in graphs

S.A. Canuto, M.G.C. Resende, and C.C. Ribeiro

Networks, vol. 38, pp. 50-58, 2001


Given an undirected graph with prizes associated with its nodes and weights associated with its edges, the prize-collecting Steiner tree problem consists in finding a subtree of this graph which minimizes the sum of the weights of its edges plus the prizes of the nodes not spanned. In this paper, we describe a multi-start local search algorithm for the prize-collecting Steiner tree problem, based on the generation of initial solutions by a primal-dual algorithm using perturbed node prizes. Path-relinking is used to improve the solutions found by local search and variable neighborhood search is used as a post-optimization procedure. Computational experiments involving different algorithm variants are reported.  Our results show that the local search with perturbations approach found optimal solutions on nearly all of the instances tested.

PostScript file of full paper

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice