Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

Research output: Contribution to journalArticleScientificpeer-review

244 Downloads (Pure)

Abstract

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997].
Original languageEnglish
Pages (from-to)225-246
JournalMathematical Programming
Volume122
Issue number2
Publication statusPublished - 2010

Fingerprint

Semidefinite Programming Relaxation
Quadratic Assignment Problem
Symmetry Group
Global optimization
Global Optimization
Lower bound
Libraries

Cite this

@article{73287c803bc240c4b02d452cf88e810a,
title = "Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem",
abstract = "We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997].",
author = "{de Klerk}, E. and R. Sotirov",
note = "Appeared earlier as CentER DP 2007-44",
year = "2010",
language = "English",
volume = "122",
pages = "225--246",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",
number = "2",

}

Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. / de Klerk, E.; Sotirov, R.

In: Mathematical Programming, Vol. 122, No. 2, 2010, p. 225-246.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

AU - de Klerk, E.

AU - Sotirov, R.

N1 - Appeared earlier as CentER DP 2007-44

PY - 2010

Y1 - 2010

N2 - We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997].

AB - We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB — a quadratic assignment problem library. Journal on Global Optimization, 10: 291–403, 1997].

M3 - Article

VL - 122

SP - 225

EP - 246

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -