- Quadratic assignment problem
The

**quadratic assignment problem**(**QAP**) is one of fundamentalcombinatorial optimization problems in the branch of optimization oroperations research inmathematics , from the category of thefacilities location problems.The problem models the following real-life problem:

:There are a set of "n" facilities and a set of "n" locations. For each pair of locations, a "distance" is specified and for each pair of facilities a "weight" or "flow" is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows.

The problem statement resembles that of the

assignment problem , only thecost function is expressed in terms of quadratic inequalities, hence the name.**Formal mathematical definition**The formal definition of the quadratic assignment problem is

:Given two sets, "P" ("facilities") and "L" ("locations"), of equal size, together with a

weight function "w" : "P" × "P" →**R**and a distance function "d" : "L" × "L" →**R**. Find thebijection "f" : "P" → "L" ("assignment") such that thecost function :::$sum\_\{a,bin\; P\}w(a,b)cdot\; d(f(a),\; f(b))$:is minimized.

Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as:

:$sum\_\{a,bin\; A\}w\_\{a,b\}d\_\{f(a),f(b)\}$

Computational complexity The problem is

NP-hard , so there is no knownalgorithm for solving this problem in polynomial time, and even small instances may require long computation time. TheTravelling salesman problem may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standardcombinatorial optimization problems may be written in this form.A considerable amount of research in

ant colony optimization , a biologically-inspired heuristic, has centered on solving the QAP by achieving as good an approximation as possible.**Applications**In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected

electronic component s onto aprinted circuit board or on a microchip, which is part of theplace and route stage of thecomputer aided design in electronics industry.**References*** A2.5: ND43, pg.218.

*Wikimedia Foundation.
2010.*