Title: Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework

Authors: Frederic Roupin

Addresses: CEDRIC-CNAM, 292 rue Saint-Martin, Paris 75141, Cedex 03, France

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.

DOI: 10.1504/IJMOR.2009.022879

International Journal of Mathematics in Operational Research, 2009 Vol.1 No.1/2, pp.144 - 162

Published online: 31 Jan 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article