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

Research output: Working paperDiscussion paperOther research output

364 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

Keywords

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

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