Greedy randomized adaptive search procedures (GRASP)

M.G.C. Resende

In Encyclopedia of Optimization, C. Floudas and P.M. Pardalos, eds. Kluwer Academic Publishers, vol. 2, pp. 373-382, 2001

ABSTRACT

This paper is a survey of greedy randomized adaptive search procedures (GRASP).  GRASP is a multi-start or iterative procedure where each GRASP iteration consists of a construction phase, where a feasible solution is constructed, followed by a local search procedure that finds a locally optimal solution.  The construction phase of GRASP is essentially a randomized greedy algorithm.  Repeated applications of the construction procedure yields diverse starting solutions for the local search. We review a basic GRASP, followed by enhancements to the basic procedure. We conclude by surveying operations research and industrial applications of GRASP.

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

Copyright Notice