Quadratic Assignment Problem

The quadratic assignment problem (QAP) in location Theory is the problem of locating facilities the cost of placing a facility depends on the distances from other facilities and also the interaction with other facilities. QAP was introduced by Koopmans and Beckman in 1957 who were trying to model a facilities location problem. It is possible to formulate some classic problems of combinatorial optimization, such as the traveling salesman, maximum clique and graph partitioning problems as a QAP. The QAP belongs to the class of NP-complete problems and is considered one of the most difficult combinatorial optimization problems. Exact solution strategies for the QAP have been unsuccessful for large problem (approximately N ≤ 25). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.