Quadratic assignment problem

The Quadratic assignment problem (QAP) is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities 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 of the distances multippled by the corresponding flows.

The problem statement resembles that of the assignment problem, only the cost 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 the bijection f : F → L ("assignment") such that the cost function:

$\sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b)))$

is minimized.

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

$\sum _{a,b\in A}w_{a,b}d_{f(a),f(b)}$

Computational complexity

The problem is NP-hard, i.e., requires long computation time even it its simplified cases, e.g., when all flows are equal to 1. For example, the Travelling salesman problem may be seen as a special case of QAP, if one assumes that the flows connect facilities only along a single ring, all flows having the value of 1. Many other problems of standard combinatorial optimization problems may be written in this form.

Applications

In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected electronic components onto a printed circuit board or on a microchip, which is part of the place and route stage of the computer aided design in electronics industry.