Optimization Online


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

Etienne De Klerk (e.deklerk***at***uvt.nl)
Renata Sotirov (R.Sotirov***at***uvt.nl)

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].

Keywords: quadratic assignment problem, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Mathematical Programming A, to appear. Note: Theorem 7.3 is incorrect as stated in the journal version, but correct in the version posted here.

Download: [PDF]

Entry Submitted: 06/13/2007
Entry Accepted: 06/13/2007
Entry Last Modified: 02/24/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society