Skip to main content
SpringerLink
Log in

Solving Large Quadratic Assignment Problems in Parallel

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.

Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.

In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. G. Armour and E. Buffa, "A heuristic algorithm and simulation approach to the relative allocation of facilities," Mgt. Sci., vol. 9, pp. 294–309, 1963.

    Google Scholar 

  2. A.A. Assad and W. Xu, "On lower bounds for a class of quadratic 0, 1 programs," Oper. Res. Letters, vol. 4, pp. 175–180, 1985.

    Google Scholar 

  3. M.S. Bazaraa and O. Kirca, "A branch-and-bound-based heuristic for solving the quadratic assignment problem," Naval Research Logistics Quarterly, vol. 30, pp. 287–304, 1983.

    Google Scholar 

  4. R. Burkard and U. Derigs, "Assignment and matching problems," EJOR, vol. 13, pp. 374–386, 1983.

    Google Scholar 

  5. P. Carraresi and F. Malucelli, "A new lower bound for the quadratic assignment problem," Oper. Res., vol. 40, no. S.1, pp. 22–27, 1992.

    Google Scholar 

  6. P. Carraresi and F. Malucelli, "A reformulation scheme and new lower bounds for the QAP," Dimacs Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, pp. 147–160, 1994.

    Google Scholar 

  7. J. Clausen and J.L. Träff, "Implementation of parallel branch-and-bound algorithms-experiences with the graph partitioning problem," Annals of Oper. Res., vol. 33, pp. 331–349, 1991.

    Google Scholar 

  8. J. Clausen and M. Perregaard, "Implementation of a parallel branch and bound algorithm for quadratic assignment problems on a 16 processor MEIKO i860 hypercube," Tech. Report, DIKU, 1994.

  9. J. Crouse and P. Pardalos, "A parallel algorithm for the quadratic assignment problem," Proceedings of Supercomputing '89, ACM Press, pp. 351–360, 1989.

  10. A. Elshafei, "Hospital lay-out as a quadratic assignment problem," Oper. Res. Quaterly, vol. 28, pp. 167–179, 1977.

    Google Scholar 

  11. S.W. Hadley, F. Rendl, and H. Wolkowicz, "A new lower bound via projection for the quadratic assignment problem," Math. of Oper. Res., vol. 17, pp. 727–739.

  12. R. Jonker and A. Volgenant, "Improving the Hungarian assignment algorithm," Operations Research Letters, vol. 5, pp. 171–175, 1986.

    Google Scholar 

  13. P.S. Laursen, "Simple approaches to parallel branch and bound," Parallel Computing, vol. 19, pp. 143–152, 1993.

    Google Scholar 

  14. T. Mautor and C. Roucaurol, "A new exact algorithm for the solution of quadratic assignment problems," Discrete Applied Mathematics, vol. 55, pp. 281–293, 1994.

    Google Scholar 

  15. C. Nugent, T. Vollmann, and J. Ruml, "An experimental comparison of techniques for the assignment of facilities to locations," Oper. Res., vol. 16, pp. 150–173, 1968.

    Google Scholar 

  16. F. Rendl, "Ranking scalar products to improve bounds for the quadratic assignment problem," EJOR, vol. 20, pp. 363–372, 1985.

    Google Scholar 

  17. F. Rendl and H. Wolkowicz, "Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem," Math. Prog., pp. 63–78, 1992.

  18. C. Roucaurol, "A parallel branch and bound algorithm for the quadratic assignment problem," Discr. Appl. Math., vol. 18, pp. 211–225, 1987.

    Google Scholar 

  19. M. Scriabin and R. Vergin, "Comparison of computer algorithms and visual based methods for plant layout," Mgt. Sci., vol. 22, pp. 172–181, 1975.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DIKU, Dept. of Computer Science, University of Copenhagen, Universitetsparken 1, DK 2100, Copenhagen Ø

    Jens Clausen & Michael Perregaard

Authors
  1. Jens Clausen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Perregaard
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Clausen, J., Perregaard, M. Solving Large Quadratic Assignment Problems in Parallel. Computational Optimization and Applications 8, 111–127 (1997). https://doi.org/10.1023/A:1008696503659

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008696503659

Search

Navigation