Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry (Q431008): Difference between revisions

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced by \textit{Q. Zhao} et al. [J. Comb. Optim. 2, No. 1, 71--109 (1998; Zbl 0904.90145)]. 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 by \textit{E. de Klerk} and \textit{R. Sotirov} [Math. Program. 122, No. 2 (A), 225--246 (2010; Zbl 1184.90120)]. Continuing in the same vein, the authors show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate their approach, they compute improved lower bounds for several instances from the QAP library QAPLIB.