Quadratic assignment problem

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems. It was originally proposed by Tjalling Koopmans and Martin J. Beckmann.^[1]

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, except that the cost function is expressed in terms of quadratic inequalities, hence the name.

The formal definition of the quadratic assignment problem is as follows.^[2]

Given a positive integer n {\displaystyle n} and n 4 {\displaystyle n^{4}} cost coefficients { c i , j , p , q } {\displaystyle \{c_{i,j,p,q}\}} , find the n × n {\displaystyle n\times n} matrix [ x i j ] {\displaystyle [x_{ij}]} that minimizes the objective function

∑ i , j ∑ p , q c i , j , p , q x i , j x p , q {\displaystyle \sum _{i,j}\sum _{p,q}c_{i,j,p,q}x_{i,j}x_{p,q}}

subject to the constraints

∑ j x i , j = ∑ i x i , j = 1 , {\displaystyle \sum _{j}x_{i,j}=\sum _{i}x_{i,j}=1,}

x i j ∈ { 0 , 1 } {\displaystyle x_{ij}\in \{0,1\}}

The quadratic assignment problem was originally posed by Tjalling Koopmans and Martin J. Beckmann in the following form.

Given square matrices D and T, find the permutation matrix X that minimizes the double-dot product of T with A = X D X ⊺ {\displaystyle A=XDX^{\intercal }} .

In other words, given D and T, find { x i j } 1 ≤ i , j ≤ n {\displaystyle \{x_{ij}\}_{1\leq i,j\leq n}} so as to

minimize ∑ 1 ≤ i , j ≤ n a i j t i j subject to ∑ 1 ≤ k ≤ n x i k = ∑ 1 ≤ k ≤ n x j k = 1 , x i j ∈ { 0 , 1 } . {\begin{aligned}{\text{minimize}}\quad &\sum _{1\leq i,j\leq n}a_{ij}t_{ij}\\{\text{subject to}}\quad &\sum _{1\leq k\leq n}x_{ik}=\sum _{1\leq k\leq n}x_{jk}=1,\\&x_{ij}\in \{0,1\}.\end{aligned}}

Using the terminology above, the matrix D tabulates the distance ( d i j {\displaystyle d_{ij}} gives the distance from location i to location j) and T the flow ( t i j {\displaystyle t_{ij}} gives the quantity of supplies to be transported from facility i to facility j.) The permutation matrix X represents an assignment of facilities to locations ( x i j {\displaystyle x_{ij}} is 1 only if facility i is located at location j.)^[2]

Intuitively, the objective function encourages facilities with high flows between each other to be placed close together.

The problem is NP-hard, so there is no known algorithm for solving this problem in polynomial time, and even small instances may require long computation time. It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P = NP.^[3] The travelling salesman problem (TSP) 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 and all distances are equal to the respective distances of the TSP instance. Many other problems of standard combinatorial optimization problems may be written in this form.

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 computer aided design in the electronics industry.

The QAP has also been used to model the cost of character placement on a keyboard. In this case, the locations are keys on the keyboard and their pairwise distances correspond to the time required to press a given pair of keys. The facilities are characters and their weights are proportional to how often the given pair of characters occur in a text corpus. This type of QAP model was used in the design of the French keyboard standard (NF Z71-300).^[4]

• Quadratic bottleneck assignment problem

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, pg.218.

• https://doi.org/10.7488/ds/3428 QAPLIB - A Quadratic Assignment Problem Library
• http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/^{[dead link]} MAOS-QAP - Java-based Quadratic Assignment Problem Solver
• https://CRAN.R-project.org/package=qap - R package qap: Heuristics for the Quadratic Assignment Problem
• https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Metaheuristic QAP solver for Windows 10/11