zbMATH — the first resource for mathematics

Improved discrete reformulations for the quadratic assignment problem. (English) Zbl 1382.90048
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 193-203 (2013).
Summary: This paper presents an improved as well as a completely new version of a mixed integer linear programming (MILP) formulation for solving the quadratic assignment problem (QAP) to global optimum. Both formulations work especially well on instances where at least one of the matrices is sparse. Modification schemes, to decrease the number of unique elements per row in symmetric instances, are presented as well. The modifications will tighten the presented formulations and considerably shorten the computational times. We solved, for the first time ever to proven optimality, the instance esc32b from the quadratic assignment problem library, QAPLIB.
For the entire collection see [Zbl 1263.68017].

90B80 Discrete location and assignment
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
Full Text: DOI