A Greedy Randomized Adaptive Search Procedure for  the Quadratic Assignment Problem

Yong Li, Panos M. Pardalos, and Mauricio G.C. Resende

In Quadratic assignment and related problems, P.M. Pardalos and H. Wolkowicz, Eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 16, pp. 237-261, 1994

ABSTRACT

A greedy randomized adaptive search procedure (GRASP) is a randomized heuristic that has been shown to quickly produce good quality solutions for a wide variety of combinatorial optimization problems. In this paper, we describe a GRASP for the quadratic assignment problem.  We review basic concepts of GRASP:  construction and localsearch algorithms.  The implementation of GRASP for the quadratic assignment problem is described in detail.  Computational experience on a large set of standard test problems (QAPLIB) is presented.

PDF file of full paper
Go back
Mauricio G.C. Resende's Home Page
Last modified: 12 October 2005

Copyright Notice