Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework

Frederic Roupin

International Journal of Mathematics in Operational Research, 2009, vol. 1, issue 1/2, 144-162

Abstract: In this article, we consider partial Lagrangian relaxations of continuous quadratic formulations of the quadratic assignment problem (QAP) where the assignment constraints are not relaxed. These relaxations are a theoretical limit for semidefinite relaxations of the QAP using any linearised quadratic equalities made from the assignment constraints. Using this framework, we survey and compare standard semidefinite relaxations of this classical NP-hard problem. In particular, this approach is a simple way to prove that some well-known semidefinite relaxations for the QAP are equivalent. Nevertheless, these relaxations have a different numerical behaviour and practical usefulness depending on the semidefinite programming solver. We discuss such issues by reporting some computational experiments.

Keywords: Lagrangian relaxation; QAP; quadratic assignment problem; SDP; semidefinite programming. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=22879 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:1:y:2009:i:1/2:p:144-162

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().