[ROU07] Semidefinite Relaxations for the QAP : A Lagrangian Point of View

Conférences invitées : ECCO XX, Limassol, Cyprus, January 2007, pp.39,

Auteurs: F. Roupin

motcle:

Résumé: We consider partial lagrangian relaxations of continuous quadratic formulations of the Quadratic Assignment Problem (QAP) where the assignment constraints are not relaxed. Applying the results of [3,4], these relaxations are a theoretical limit for semidefinite relaxations of the QAP using any linearized quadratic equalities made from the assignment constraints. Moreover, given any such semidefinite relaxation, the condition to reach the value of the corresponding partial lagrangian relaxation is presented in [3]. Since all the constant quadratic fonctions over an affine variety are known [3], we can use this framework to design and compare semidefinite relaxations. In particular, it is a simple way to prove that several well-known [1,2,5,6] semidefinite relaxations for the QAP are equivalent [7], although their numerical behavior is different and can depend on the solver used. This motivates the search for other efficient cuts in order to achieve stronger bounds. Besides, as noticed in [2], adding cuts can speed up the solving process. Hence, one can obtain a better bound without increasing the total computing time, although the number of constraints in the semidefinite relaxation is larger. This makes such cutting plane algorithms a promising approach to solve difficult instances of the QAP. [1] S. Burer and D. Vandenbussche. Solving Lift-and-Project Relaxations of Binary Integer Programs. SIAM Journal on Optimization 16(3):726-750, 2006. [2] A. Faye and F. Roupin. A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem. In ESA 2005, Mallorca, Spain, October 3-6, 2005. LNCS 3669, pp. 850-861, 2005. [3] A. Faye and F. Roupin. Partial Lagrangian relaxation for General Quadratic Programming. 4'OR Vol 5(1):75-88, 2007. [4] C. LemarÃ©chal and F. Oustry, Semidefinite relaxations in combinatorial optimization from a lagrangian point of view. In N. Hadjisavvas and P.M. Pardalos, editors, Advances in Convex Analysis and Global Optimization, Kluwer, pp. 119-134, 2001. [5] F. Rendl, R. Sotirov: Bounds for the quadratic assignment problem using the bundle method. To appear in Mathematical Programming B. [6] F. Roupin. From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems. Journal of Combinatorial Optimization, 8(4): 469-493, 2004. [7] F. Roupin. Algorithmes Combinatoires et Relaxations par Programmation LinÃ©aire et SemidÃ©finie. Application Ã la RÃ©solution de ProblÃ¨mes Quadratiques et d'Optimisation dans les Graphes. Habilitation Ã Diriger des Recherches en Informatique de l'UniversitÃ© Paris Nord, 2006. Available at http://cedric.cnam.fr.

Collaboration: LIPN

BibTeX

@inproceedings {
	ROU07,
	title	=	"{Semidefinite Relaxations for the QAP : A Lagrangian Point of View}",
	author	=	" F. Roupin ",
	booktitle	=	"{ECCO XX, Limassol, Cyprus}",
	year	=	2007,
	month	=	"January",
	pages	=	"39",
}