Optimization Online


GRASP: Basic components and enhancements

Paola Festa(paola.festa***at***unina.it)
Mauricio G. C. Resende(mgcr***at***research.att.com)

Abstract: GRASP (Greedy Randomized Adaptive Search Procedures) is a multistart metaheuristic for producing good-quality solutions of combinatorial optimization problems. Each GRASP iteration is usually made up of a construction phase, where a feasible solution is constructed, and a local search phase which starts at the constructed solution and applies iterative improvement until a locally optimal solution is found. While, in general, the construction phase of GRASP is a randomized greedy algorithm, other types of construction procedures have been proposed. Repeated applications of a construction procedure yields diverse starting solutions for the local search. This chapter gives an overview of GRASP describing its basic components and enhancements to the basic procedure, including reactive GRASP and intensification strategies.

Keywords: GRASP, metaheuristics, hybrid heuristics, heuristics

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, July 2008.

Download: [PDF]

Entry Submitted: 07/08/2008
Entry Accepted: 07/11/2008
Entry Last Modified: 07/08/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society