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

Auteurs: A. Faye , F. Roupin

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

BibTeX

@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",
}