Algorithm 769: Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP

ABSTRACT

We describe Fortran subroutines for finding approximate solutions of sparse instances of the Quadratic Assignment Problem (QAP) using a Greedy Randomized Adaptive Search Procedure (GRASP). The design and implementation of the code are described in detail. Computational results comparing the new subroutines with a dense version of the code (Algorithm 754, ACM TOMS) show that the speedup increases with the sparsity of the data.

REFERENCES

• 1: BURKARD, R., KARISCH, S., AND RENDL, F. 1991. QAPLIB: A quadratic assignment problem library. Eur. J. Oper. Res. 55, 115-119.
• 2: FEO, T. AND RESENDE, M. 1995. Greedy randomized adaptive search procedures. J. Global Optim. 6, 109-133.
• 3: KOOPMANS, T. AND BECKMANN, M. 1957. Assignment problems and the location of economic activities. Econometrica 25, 53-76.
• 4: LI, Y., PARDALOS, P., AND RESENDE, M. 1994. A greedy randomized adaptive search procedure for the quadratic assignment problem. In Quadratic Assignment and Related Problems. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 16. American Mathematical Society, Providence, R.I., 237-261.
• 5: PARDALOS, P. AND WOLKOWICZ, H., Eds. 1994. Quadratic Assignment and Related Problems. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 16, American Mathematical Society, Providence, R.I.
• 6: PARDALOS, P., PITSOULIS, L., AND RESENDE, M. 1995. A parallel GRASP implementation for the quadratic assignment problem. In Parallel Algorithms for Irregularly Structured Problems. Kluwer Academic Publishers, Hingham, Mass., 111-130.
• 7: Mauricio G. C. Resende , Panos M. Pardalos , Yong Li, Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.104-118, March 1996 [doi>10.1145/225545.225553]
• 8: Linus Schrage, A More Portable Fortran Random Number Generator, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.132-138, June 1979 [doi>10.1145/355826.355828]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Performance

Keywords:
Fortran subroutines, GRASP, combinatorial optimization, local search, quadratic assignment problem