Article ID: | iaor20123249 |
Volume: | 220 |
Issue: | 2 |
Start Page Number: | 314 |
End Page Number: | 319 |
Publication Date: | Jul 2012 |
Journal: | European Journal of Operational Research |
Authors: | Westerlund Tapio, Nyberg Axel |
Keywords: | programming: integer, programming: nonlinear |
The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP‐hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non‐linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size