Algorithm 754: FORTRAN Subroutines for Approximate Solution of Dense Quadratic Assignment Problems using GRASP

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

ACM Transactions on Mathematical Software, vol. 22, pp. 104-118, 1996

ABSTRACT

In the NP-complete quadratic assignment problem (QAP), N facilities are to be assigned to N sites at minimum cost.  The contribution of assigning facility I to site K and facility J to site L to the total cost is F(I,J) * D(K,L), where F(I,J) is the flow between facilities I and J, and D(K,L) is the distance between sites K and L. Only very small (N less than or equal to 20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions.  This paper describes a set of FORTRAN subroutines to find approximate solutions to dense quadratic assignment problems, having at least one symmetric flow or distance matrix.  A greedy randomized adaptive search procedure (GRASP) is used to produce the solutions.  The design and implementation of the code are described in detail, and extensive computational experiments are reported, illustrating solution quality as a function of running time.

PostScript file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 26 June 2002

Copyright Notice