ALGORITHM 754 - FORTRAN SUBROUTINES FOR APPROXIMATE SOLUTION OF DENSEQUADRATIC ASSIGNMENT PROBLEMS USING GRASP

In the NP-complete quadratic assignment problem (QAP), n facilities ar e to be assigned to n sites at minimum cost. The contribution of assig ning facility i to site k and facility j to site l to the total cost i s f(ij) . d(kl), where f(ij) is the flow between facilities i and j, a nd d(kl) is the distance between sites k and l. Only very small (n les s than or equal to 20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions. Th is article 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 sear ch procedure (GRASP) is used to produce the solutions. The design and implementation of the code are described in detail, and extensive comp utational experiments are reported, illustrating solution quality as a function of running time.