Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Research output: Contribution to journalArticleScientificpeer-review

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

Quadratic Assignment Problem
Semidefinite Programming
Symmetry
Automorphism Group
Veins
Lower bound

Cite this

@article{16de0b3662384300a29bbb8ebec54a1e,
title = "Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry",
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.",
author = "{de Klerk}, E. and R. Sotirov",
year = "2012",
doi = "10.1007/s10107-010-0411-5",
language = "English",
volume = "133",
pages = "75--91",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "1",

}

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. / de Klerk, E.; Sotirov, R.

In: Mathematical Programming, Vol. 133, No. 1, 2012, p. 75-91.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

AU - de Klerk, E.

AU - Sotirov, R.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/s10107-010-0411-5

DO - 10.1007/s10107-010-0411-5

M3 - Article

VL - 133

SP - 75

EP - 91

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -