• A STUDY ON QUADRATIC ASSIGNMENT PROBLEM AND ITS APPLICATIONS

Abstract

The Quadratic Assignment Problem (QAP) is one of the most interesting and most challenging combinatorial optimization problems in existence. It is considered to be one of the most difficult problems in the NP-hard class, models many applications in several areas such as operational research, parallel and distributed computing, and combinatorial data analysis. Since QAP is NP-complete, it is notoriously difficult to be solved by exact solution methods. This paper aims at describing the state of the art on quadratic assignment problems (QAPs). An introduction discussing the origins of the problem will be provided first. Next, formal problem descriptions and mathematical formulations will be given. Then the lower bounds, exact algorithms and heuristic algorithms will also be discussed. Finally, some applications of the QAP will be analyzed.