|
 
|
[Rou09] Semidefinite relaxations of the Quadratic Assignment Problem in a Lagrangian Framework
Revue Internationale avec comité de lecture : Journal Int. J. of Mathematics in Operational Research, vol. 1(1), pp. 144-162, 2009, (doi:10.1504/IJMOR.2009.022879)
motcle:
Résumé:
In this paper, 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 linearized 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 behavior and practical usefulness depending on the
semidefinite programming solver. We discuss such issues by reporting some computational experiments.
Commentaires:
note
Equipe:
Collaboration:
LIPN
BibTeX
| @article { | |||
| Rou09, | |||
| title | = | "{Semidefinite relaxations of the Quadratic Assignment Problem in a Lagrangian Framework}", | |
| author | = | "F. Roupin", | |
| journal | = | "Int. J. of Mathematics in Operational Research", | |
| year | = | 2009, | |
| volume | = | 1, | |
| number | = | 1, | |
| pages | = | "144-162", | |
| note | = | "{note}", | |
| doi | = | "10.1504/IJMOR.2009.022879", | |
| } | |||
