A Survey of the Quadratic Assignment Problem, with Applications

Abstract

The Quadratic Assignment Problem (QAP) is one of the most interesting and most challenging combinatorial optimization problems in existence.This paper will be a survey of the QAP.An introduction discussing the origins of the problem will be provided first.Next, formal problem descriptions and mathematical formulations will be given.Issues pertaining to the computational complexity of the QAP, lower bounds and exact algorithms will also be addressed.Some commonly used heuristic procedures will then be introduced.Finally, some applications of the QAP will by analyzed.