Treffer: A Parallel GRASP Implementation for the Quadratic Assignment Problem

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. 1 Introduction Nonlinear assignment problems, such as quadratic, cubic, and N-adic assignment problems were formulated by Lawler [11]. One of the most extensively studied nonlinear assignment problems is the quadratic assignment problem (QAP). The QAP was first introduced by Koopmans and Beckmann in 1957 as a mathematical model for locating a set of indivisible economic activities [9]. Consider th.