|
 
|
[EL16a] Comparison of Quadratic Convex Reformulations to solve the Quadratic Assignment Problem
Conférence Internationale avec comité de lecture : COCOA 2016, December 2016, pp.726--734, Series LNCS, China, (DOI: 10.1007/978-3-319-48749-6_54)Mots clés: Quadratic Assignment Problem, Convex Quadratic Programming, Semidefinite Programming, Experiments
Résumé:
We consider the $(QAP)$ that consists in minimizing a quadra\-tic function subject to assignment constraints where the variables are binary. In this paper, we build two families of equivalent quadratic convex formulations of $(QAP)$. The continuous relaxation of each equivalent formulation is then a convex problem and can be used within a B\&B. In this work, we focus on finding the "best" equivalent formulation within each family, and we prove that it can be computed using semidefinite programming. Finally, we get two convex formulations of $(QAP)$ that differ from their sizes and from the tightness of their continuous relaxation bound. We present computational experiments that prove the practical usefulness of using quadratic convex formulation to solve instances of $(QAP)$ of medium sizes.
BibTeX
| @inproceedings { | |||
| EL16a, | |||
| title | = | "{Comparison of Quadratic Convex Reformulations to solve the Quadratic Assignment Problem}", | |
| author | = | " S. Elloumi and A. Lambert ", | |
| booktitle | = | "{COCOA 2016}", | |
| year | = | 2016, | |
| edition | = | "Springer", | |
| month | = | "December", | |
| series | = | "LNCS", | |
| pages | = | "726--734", | |
| address | = | " China", | |
| doi | = | "10.1007/978-3-319-48749-6_54", | |
| } | |||
