Optimization Online


A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

E. de Klerk(edeklerk***at***ntu.edu.sg)
R. Sotirov(r.sotirov***at***uvt.nl)
U. Truetsch(U.Truetsch***at***uvt.nl )

Abstract: Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the restrictive size of the early relaxations. Some recent progress has been made by studying smaller SDP relaxations and by exploiting group symmetry in the QAP data. In this work we introduce a new SDP relaxation where the matrix variables are only of the order of the QAP dimension, and we show how one may exploit group symmetry in the problem data for this relaxation. We also provide a detailed numerical comparison with related bounds from the literature.

Keywords: quadratic assignment problem, semidenite programming bounds.

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 08/08/2013
Entry Accepted: 08/08/2013
Entry Last Modified: 08/08/2013

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 Optimization Society