Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem

Research output: Working paperDiscussion paperOther research output

243 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]. AMS classification: 90C22, 20Cxx, 70-08.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages21
Volume2007-44
Publication statusPublished - 2007

Publication series

NameCentER Discussion Paper
Volume2007-44

Fingerprint

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

Keywords

  • quadratic assignment problem
  • semidefinite programming
  • group sym- metry

Cite this

@techreport{87a5d12686e548638ea51a76fc5f25e7,
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]. AMS classification: 90C22, 20Cxx, 70-08.",
keywords = "quadratic assignment problem, semidefinite programming, group sym- metry",
author = "{de Klerk}, E. and R. Sotirov",
note = "Subsequently published in Mathematical Programming, 2010 Pagination: 21",
year = "2007",
language = "English",
volume = "2007-44",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem. / de Klerk, E.; Sotirov, R.

Tilburg : Operations research, 2007. (CentER Discussion Paper; Vol. 2007-44).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem

AU - de Klerk, E.

AU - Sotirov, R.

N1 - Subsequently published in Mathematical Programming, 2010 Pagination: 21

PY - 2007

Y1 - 2007

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]. AMS classification: 90C22, 20Cxx, 70-08.

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]. AMS classification: 90C22, 20Cxx, 70-08.

KW - quadratic assignment problem

KW - semidefinite programming

KW - group sym- metry

M3 - Discussion paper

VL - 2007-44

T3 - CentER Discussion Paper

BT - Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem

PB - Operations research

CY - Tilburg

ER -