# [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