Parallel Greedy Randomized Adaptive Search Procedures

Mauricio G. C. Resende (mgcrresearch.att.com)
Celso C. Ribeiro (celsoinf.puc-rio.br)

Abstract: A GRASP (Greedy Randomized Adaptive Search Procedure) is a metaheuristic for producing good-quality solutions of combinatorial optimization problems. It is usually implemented with a construction procedure based on a greedy randomized algorithm followed by local search. In this Chapter, we survey parallel implementations of GRASP. We describe simple strategies to implement independent parallel GRASP heuristics and more complex cooperative schemes using a pool of elite solutions to intensify the search process. Some applications of independent and cooperative parallelizations are presented in detail.

Keywords: Combinatorial optimization, local search, GRASP, path-relinking, parallel algorithm

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: AT&T Labs Research Technical Report TD-67EKXH. December 6, 2004.

Download: [PDF]

Entry Submitted: 12/06/2004
Entry Accepted: 12/07/2004
Entry Last Modified: 12/06/2004

Modify/Update this entry