Its range of applications is wide, including facility location, keyboard layout, and various other domains.
The key success factor of specialized branch-and-bound frameworks for minimizing QAPs is an efficient implementation of a strong lower bound.
In this talk, we propose a lower-bound preserving transformation of a QAP to a different quadratic problem allowing for small and efficiently solvable SDP relaxations. This transformation is self-tightening in a branch-and-bound process. Experimental evaluations show promising results, in particular for instances with a small width in one of the dimensions.