### Abstract

Original language | English |
---|---|

Pages (from-to) | 75-91 |

Journal | Mathematical Programming |

Volume | 133 |

Issue number | 1 |

Early online date | 24 Sep 2010 |

DOIs | |

Publication status | Published - 2012 |

### Fingerprint

### Cite this

}

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

Research output: Contribution to journal › Article › Scientific › peer-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 -