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 linearization are tight, but hardly exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation [1] is the smallest of these linearizations, but very weak. In this paper, we analyze how Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As we show in our numerical experiments, these tightened formulations remain small but computationally effective in order to solve the QAP by means of general purpose MILP solvers.
Citation
Statistics and Operations Research,Rey Juan Carlos University (URJC),C/ Tulipán s/n, 28933,Móstoles (Madrid),Spain 04/2010