The QAP in the trace formulation is modelled as the minimization of a quadratic function over the permutation matrices. The set of permutation matrices can be represented by quadratic constraints. Relaxations of these constraints are used in branch and bound solution methods. These relaxations include the eigenvalue and projected eigenvalue relaxations, as well as various semidefinite programming, SDP, and doubly nonnegative, DNN, relaxations. These latter relaxations are particularly strong and often solve the QAP to optimality. However, they can be extremely expensive to solve.
We show that the combination of an alternating directions method of multipliers, ADMM, in combination with facial reduction works extremely well in solving the very difficult DNN relaxation.