METHODS OF USING THE QUADRATIC ASSIGNMENT PROBLEM SOLUTION

Background: Quadratic assignment problem (QAP) is one of the most interesting of combinatorial optimization. Was presented by Koopman and Beckamanna in 1957, as a mathematical model of the location of indivisible tasks. This problem belongs to the class NP-hard issues. This forces the application to the solution already approximate methods for tasks with a small size (over 30).
Even though it is much harder than other combinatorial optimization problems, it enjoys wide interest because it models the important class of decision problems.

Material and methods: The discussion was an artificial intelligence tool that allowed to solve the problem QAP, among others are: genetic algorithms, Tabu Search, Branch and Bound.

Results and conclusions: QAP did not arise directly as a model for certain actions, but he found its application in many areas. Examples of applications of the problem is: arrangement of buildings on the campus of the university, layout design of electronic components in systems with large scale integration (VLSI), design a hospital, arrangement of keys on the keyboard.