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 PageLast modified: 26 June 2002