A branch‐and‐bound‐based heuristic for solving the quadratic assignment problem

M. S. Bazaraa and O. Kirca

Naval Research Logistics Quarterly, 1983, vol. 30, issue 2, 287-304

Abstract: In this article a branch‐and‐bound algorithm is proposed for solving the quadratic assignment problem. Using symmetric properties of the problem, the algorithm eliminates “mirror image” branches, thus reducing the search effort. Several routines that transform the procedure into an efficient heuristic are also implemented. These include certain 2‐way and 4‐way exchanges, selective branching rules, and the use of variable upper‐bounding techniques for enhancing the speed of fathoming. The computational results are quite encouraging. As an exact scheme, the algorithm solved the 12‐facility problem of Nugent et al. and the 19‐facility problem of Elshafei. More importantly, as a heuristic, the procedure produced the best known solutions for all well‐known problems in the literature, and produced improved solutions in several cases.

Date: 1983
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800300210

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:30:y:1983:i:2:p:287-304

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().