QAP

The Quadratic Assignment Problem (QAP) is one of the most interesting and most challenging combinatorial optimization problems in existence. The quadratic assignment problem (QAP) was originally introduced in 1957 by Tjalling C. Koopmans and Martin Beckman who were trying to model a facilities location problem [9].

Since then, it has been among the most studied problems in all of combinatorial optimization. Many scientists including mathematicians, computer scientists, operations research analysts, and economists have used the QAP to model a variety of optimization problems. The approach is to have two matrices of size n×m given as:

The objective is then to find the permutation π∗ which minimizes

where Π(n) is a set of permutations of n elements. QAP is considered a NP hard problem and problem sizes larger than 20 are considered intractable.