Semidefinite Optimization for solving the Quadratic Assignment Problem

The Quadratic Assignment Problem is one of the most challenging combinatorial optimizationproblems. It has brought considerable attention since many industrial andreal lifeapplications can be formulated as QAPs.
We present a survey of the semidefinite approaches in a unified framework. Special emphasis is put on the design of the models that has strongly depended on solvers that were available at that moment.
First, we give a new proof of a characterization lemma for redundant quadratic equalities for general quadratic problems.
Second, specializing this result to a quadratic formulation of the QAP, we can review the semidefinite relaxations proposed so far and compare them straightforwardly.
Furthermore, another positive side effect of our approach is to provide mechanically new equivalent relaxations that may be more efficient on practical grounds.

Homepage of Frédéric Roupin