\input zb-basic
\input zb-ioport
\iteman{io-port 06119361}
\itemau{Nyberg, Axel; Westerlund, Tapio}
\itemti{A new exact discrete linear reformulation of the quadratic assignment problem.}
\itemso{Eur. J. Oper. Res. 220, No. 2, 314-319 (2012).}
\itemab
Summary: 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 $n=32$ and $64$), from the quadratic assignment problem library, QAPLIB.
\itemrv{~}
\itemcc{}
\itemut{combinatorial optimization; quadratic assignment problem; discrete linear reformulation; mixed integer programming; global optimization}
\itemli{doi:10.1016/j.ejor.2012.02.010}
\end