Improved SDP bounds for the Quadratic Assignment Problem with suitable symmetry
Renata Sotirov

The Quadratic Assignment Problem (QAP) is a well-known NP-hard problem, and even
small instances are notoriously difficult to solve in practice.

Semidefinite programming (SDP) bounds for the QAP were introduced in 1998. These
bounds are quite strong, but computationally demanding. For QAP instances where
the data matrices have large automorphism groups, the SDP bounds can be computed
more efficiently, as was shown in:

[E. de Klerk and R. Sotirov. Exploiting group symmetry in semidefinite programming
relaxations of the quadratic assignment problem, 
{\em Mathematical Programming A}, (to appear)].

In this talk we show how one may obtain even stronger SDP bounds for QAP instances
where one of the data matrices has a transitive automorphism group. To illustrate
our approach, we compute improved lower bounds for several instances from the QAP
library QAPLIB.