A Parallel GRASP Implementation for the Quadratic Assignment Problem

P.M. Pardalos, L.S. Pitsoulis, and M. G. C. Resende

In Parallel Algorithms for Irregular Problems, A. Ferreira and J. Rolim, eds, Kluwer Academic Publishers, pp. 111-130, 1995


In this paper we present a parallel implementation of a Greedy Randomized Adaptive Search Procedure GRASP for finding approximate
solutions to the quadratic assignment problem.  In particular, we discuss efficient techniques for large-scale sparse quadratic assignment problems on an MIMD parallel computer.  We report computational experience on a collection of quadratic assignment problems.  The code was run on a Kendall Square Research KSR-1 parallel computer, using 1, 4, 14, 24, 34, 44, 54, and 64 processors, and achieves an average speedup that is almost linear in the number of processors.

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

Copyright Notice