Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71–109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these 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, Mathematical Programming A, (to appear)]. Continuing in the same vein, we show how one may obtained stronger 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.
Citation
CentER Discussion Paper Tilburg University, The Netherlands, September 2009.