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

E. de Klerk; R. Sotirov

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

E. de Klerk, R. Sotirov

Research output: Contribution to journal › Article › Scientific › peer-review

52 Citations (Scopus)

320 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 language	English
Pages (from-to)	225-246
Journal	Mathematical Programming
Volume	122
Issue number	2
Publication status	Published - 2010

Access to Document

Exploiting1

Fingerprint Dive into the research topics of 'Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem'. Together they form a unique fingerprint.

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",

}

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 -