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

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

ABSTRACT

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

Copyright Notice