A Disjunctive Programming Approach to the Quadratic Assignment Problem Using Benders' Decomposition

The first version of the quadratic assignment problem (QAP) was posed by Koopmans and Beckmann in 1957. Despite the vast number of publications on the QAP, many small instances are not yet solved to optimality. Some of the most effective modern methods for solving the QAP stem from the Kaufman-Broeckx linearization. In order to advance which QAP instances can be solved, a new method for solving the QAP is proposed. This method has been derived using disjunctive programming, and Benders' decomposition. This method uses mixed integer programming and branch and cut, and this method is closely related to the Kaufman-Broeckx linearization. A prototype of the proposed method is evaluated computationally.