Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
A lower bound for the Quadratic Assignment Problem based upon a semidefinite relaxation and a cutting planes approach
[FR04] A lower bound for the Quadratic Assignment Problem based upon a semidefinite relaxation and a cutting planes approach
Conférence Internationale avec comité de lecture : ECCO 2004, Beirut, Lebanon, January 2004,
motcle:
Résumé:
Usually, cutting plane algorithms work by solving a sequence of linear programming relaxations of an integer programming problem. In this paper, we describe experiments for the Quadratic Assignment Problem [2], using a semidefinite relaxation proposed in [4] strengthened by a cutting planes approach. This new lower bound is compared with the ones obtained by linear [1,3] and semidefinite approaches [4,5]. Our tests show that the cuts we use (presented in [1]) allow to improve significantly on the bounds obtained by using only semidefinite programming. Moreover, this is achievied with a moderate additionnal computing time. Indeed, thanks to the strong tailing off effect of the SDP solver we have used (SB, written by C. Helmberg), we can obtain in a short time an approximate solution which is suitable to generate efficient cutting planes.
[1] A. Blanchard, S. Elloumi, A. Faye and N. Wicker. Un algorithme de génération de coupes pour le problème de l'affectation quadratique. INFOR, 41(1):35-49, 2003.
[2] R.E. Burkard, S.E. Karisch and F. Rendl, QAPLIB - A Quadratic Assignment Problem Library, Journal of Global Optimization 10:391-403, 1997.
[3] M.G.C Resende, K.G. Ramakrisnhnan, and Z. Drezner, Computing lower bounds for the quaadratic assignment problem with an interior point algorithm for linear programming, Operations Research 43(5), pp. 781-791, 1995.
[4] Frédéric Roupin, From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems - TR CEDRIC 388, 2003. http://cedric.cnam.fr.
[5] Q. Zhao, S.E. Karish, F. Rendl and H. Wolkowicz, Semidefinite programming relaxations for the quadratic assignment problem, J. of Combinatorial Optimization 2(1), pp. 71-109, 1998.
keywords: Quadratic Assignment Problem, Semidefinite Programming, cutting planes
Collaboration:
LIPN
| @inproceedings { | |||
| FR04, | |||
| title | = | "{A lower bound for the Quadratic Assignment Problem based upon a semidefinite relaxation and a cutting planes approach}", | |
| author | = | " A. Faye and F. Roupin ", | |
| booktitle | = | "{ECCO 2004, Beirut, Lebanon}", | |
| year | = | 2004, | |
| month | = | "January", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |