A new bound for the quadratic assignment problem based on convex quadratic programming (Q5930731)

The authors derive a new bound for the Quadratic Assignment Problems (QAP) from a pair of dual semidefinite programs. The new bound is closely related to the Projected eigenvalue Bound (PB) for the QAP. It is shown that under mild assumptions the new bound is always strictly better than PB. Computational experiments show that it increases much faster than PB within a branch and bound process. The construction of the new bound requires a dual optimal solution (which is easy to get) for a certain linear assignment problem. For evaluating the new bound a convex quadratic program is solved via an interior point approach. The solution of this quadratic program can also be used to fix variables in the underlying QAP. The new bound offers a good trade-off between quality and computational effort.