Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem
[FR05a] A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem
Conférence Internationale avec comité de lecture : ESA'05, 3-6 octobre, Majorque, Espagne, January 2005, Vol. 3669, pp.850-861, Series LNCS,
motcle:
Résumé:
We present a cutting planes algorithm for the Quadratic Assignment Problem based upon a semidefinite relaxation,
and we report experiments for classical instances. Our lower bound is compared with the ones obtained by linear and semidefinite approaches. Our tests show that the cuts we use (originally proposed for a linear approach) allow to improve significantly on the bounds
obtained by the other approaches. Moreover, this is achieved within a moderate additional computing effort, and even in a shorter total time sometimes. Indeed, thanks to the strong tailing off effect of the SDP solver we have used (SB), we obtain in a reasonable time an approximate solution which is suitable to generate efficient cutting planes which speed up the convergence of SB.
Collaboration:
LIPN
| @inproceedings { | |||
| FR05a, | |||
| title | = | "{A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem}", | |
| author | = | " A. Faye and F. Roupin ", | |
| booktitle | = | "{ESA'05, 3-6 octobre, Majorque, Espagne}", | |
| year | = | 2005, | |
| month | = | "January", | |
| series | = | "LNCS", | |
| volume | = | 3669, | |
| pages | = | "850-861", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |