A Branch and Bound Based Heuristic for Solving the Quadratic Assignment Problem

摘要

In this paper 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. (Author)