| Article ID: | iaor20133920 |
| Volume: | 207 |
| Issue: | 1 |
| Start Page Number: | 261 |
| End Page Number: | 278 |
| Publication Date: | Aug 2013 |
| Journal: | Annals of Operations Research |
| Authors: | Ma Liang, Zhang Huizhen, Beltran-Royo Cesar |
| Keywords: | programming: integer |
The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearizations are tight, but rarely exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation (Eur. J. Oper. Res. 2(3):204–211, 1978) is the smallest of these linearizations, but very weak. In this paper, we analyze how the Kaufman and Broeckx formulation can be tightened to obtain better QAP‐MILP formulations. As shown in our numerical experiments, these tightened formulations remain small but computationally effective to solve the QAP by means of general purpose MILP solvers.