Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)

Abstract

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et al. (J Comb Optim 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 Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain 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.
Original languageEnglish
Pages (from-to)75-91
JournalMathematical Programming
Volume133
Issue number1
Early online date24 Sep 2010
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry'. Together they form a unique fingerprint.

  • Cite this