Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP 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 ij ·d kl , where f ij is the flow between facilities i and j, and d kl is the distance between sites k and l. Only very small (n≤20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions. This 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 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. (Source:

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 15 articles , 1 standard article )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Ribeiro, Celso C.; Rosseti, Isabel; Vallejos, Reinaldo: Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms (2012)
  2. Mateus, Geraldo R.; Resende, Mauricio G.C.; Silva, Ricardo M.A.: GRASP with path-relinking for the generalized quadratic assignment problem (2011)
  3. Jaramillo, Juan R.; McKendall, Alan R.: Metaheuristics for the integrated machine allocation and layout problem (2010)
  4. Ahuja, Ravindra K.; Jha, Krishna C.; Orlin, James B.; Sharma, Dushyant: Very large-scale neighborhood search for the quadratic assignment problem (2007)
  5. Duman, Ekrem; Or, Ilhan: The quadratic assignment problem in the context of the printed circuit board assembly process (2007)
  6. Loiola, Eliane Maria; De Abreu, Nair Maria Maia; Boaventura-Netto, Paulo Oswaldo; Hahn, Peter; Querido, Tania: A survey for the quadratic assignment problem (2007)
  7. Anstreicher, Kurt; Brixius, Nathan; Goux, Jean-Pierre; Linderoth, Jeff: Solving large quadratic assignment problems on computational grids (2002)
  8. Ahuja, Ravindra K.; Orlin, James B.; Tiwari, Ashish: A greedy genetic algorithm for the quadratic assignment problem (2000)
  9. Murphey, R.A.; Pardalos, P.M.; Pitsoulis, L.: A parallel grasp for the data association multidimensional assignment problem (1999)
  10. Palubeckis, G.: Generating hard test instances with known optimal solution for the rectilinear quadratic assignment problem (1999)
  11. Mavridou, T.; Pardalos, P.M.; Pistoulis, L.S.; Resende, Mauricio G.C.: A GRASP for the biquadratic assignment problem (1998)
  12. Urban, Timothy L.: Solution procedures for the dynamic facility layout problem (1998)
  13. Mason, Andrew; Rönnqvist, Mikael: Solution methods for the balancing of jet turbines (1997)
  14. Pardalos, P.M.; Ramakrishnan, K.G.; Resende, M.G.C.; Li, Y.: Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem (1997)
  15. Resende, Mauricio G.C.; Pardalos, Panos M.; Li, Yong: Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP (1996)