Optimization Online


Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem

Janez Povh (janez.povh***at***fis.unm.si)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)

Abstract: Semidefinite relaxations of the quadratic assignment problem (QAP) have recently turned out to provide good approximations to the optimal value of QAP. We take a systematic look at various conic relaxations of QAP. We first show that QAP can equivalently be formulated as a linear program over the cone of completely positive matrices. Since it is hard to optimize over this cone, we also look at tractable approximations and compare with several relaxations from the literature. We show that several of the well-studied models are in fact equivalent. It is still a challenging task to solve the strongest of these models to reasonable accuracy on instances of moderate size. We also provide a new relaxation, which gives strong lower bounds and is easy to compute.

Keywords: quadratic assignment problem, copositive programming, semidefinite relaxations, lift-and-project relaxations

Category 1: Combinatorial Optimization

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

Category 3: Integer Programming (0-1 Programming )

Citation: Povh, Janez; Rendl, Franz. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6 (2009), no. 3, 231--241.

Download: [Postscript][PDF]

Entry Submitted: 10/24/2006
Entry Accepted: 10/24/2006
Entry Last Modified: 03/21/2011

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