@inproceedings{ea7dd17ddec240cbaebf82263eb1d9be,
title = "Comparison of quadratic convex reformulations to solve the quadratic assignment problem",
abstract = "We consider the (QAP) that consists in minimizing a quadratic 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.",
keywords = "Convex quadratic programming, Experiments, Quadratic assignment problem, Semidefinite programming",
author = "Sourour Elloumi and Am{\'e}lie Lambert",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 ; Conference date: 16-12-2016 Through 18-12-2016",
year = "2016",
month = jan,
day = "1",
doi = "10.1007/978-3-319-48749-6\_54",
language = "English",
isbn = "9783319487489",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "726--734",
editor = "Minming Li and Lusheng Wang and Chan, \{T-H. Hubert\}",
booktitle = "Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings",
}