Quadratic assignment problem: Difference between revisions

Revision as of 16:38, 7 August 2013

Latest revision as of 00:22, 16 April 2025

(35 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|Combinatorial optimization problem}}

The '''quadratic assignment problem''' ('''QAP''') is one of the fundamental [[combinatorial optimization]] problems in the branch of [[Optimization (mathematics)|optimization]] or [[operations research]] in [[mathematics]], from the category of the [[Optimal facility ___location|facilities ___location]] problems first introduced by Koopmans and Beckmann.<ref>Koopmans TC, Beckmann M (1957). Assignment problems and the ___location of economic activities. Econometrica 25(1):53-76</ref>

The problem models the following real-life problem:

Line 5 ⟶ 6:

: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.

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

The problem statement resembles that of the [[assignment problem]], except that the [[Loss function|cost function]] is expressed in terms of quadratic inequalities, hence the name.

==Formal mathematical definition==

{{unreferenced-section|date=April 2024}}

The formal definition of the quadratic assignment problem is as follows:

:Given two sets, ''P'' ("facilities") and ''L'' ("locations"), of equal size, together with a [[weight function]] ''w'' : ''P'' &times; ''P'' → '''[[real number|R]]''' and a distance function ''d'' : ''L'' &times; ''L'' → '''[[real number|R]]'''. Find the [[bijection]] ''f'' : ''P'' → ''L'' ("assignment") such that the cost function:

::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math>

Line 24 ⟶ 25:

In matrix notation:

:<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDXWXD^TX^T)</math>

where <math>\Pi_n</math> areis the set of <math>n \times n</math> permutation matrices, "<math>W"</math> is the weight matrix and "<math>D"</math> is the distance matrix.

== Computational complexity ==

The problem is [[NP-hard]], so there is no known [[algorithm]] for solving this problem in [[Time complexity|polynomial time]], and even small instances may require long computation time. TheIt [[Travelling salesman problem]] may be seen as a special case of QAP ifwas onealso assumesproven that the flowsproblem connectdoes allnot facilitieshave onlyan alongapproximation aalgorithm singlerunning ring,in allpolynomial flowstime havefor the same non-zeroany (constant) value.factor, Many otherunless problemsP of= standardNP.<ref>{{Cite [[combinatorialjournal|title optimization]]= problemsP-Complete mayApproximation be written in this form.Problems

|last1 = Sahni|first1 = Sartaj

|last2 = Gonzalez |first2 = Teofilo

|date = July 1976

|volume=23 |issue=3

|pages = 555–565

|journal = Journal of the ACM|doi = 10.1145/321958.321975|hdl = 10338.dmlcz/103883

|hdl-access = free}}</ref> 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.

== 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 a [[printed circuit board]] or on a [[integrated circuit|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).<ref name="t142">{{cite book | last=John | first=Maximilian | last2=Karrenbauer | first2=Andreas | title=Mathematical Optimization Theory and Operations Research | chapter=Dynamic Sparsification for Quadratic Assignment Problems | publisher=Springer International Publishing | publication-place=Cham | volume=11548 | date=2019 | isbn=978-3-030-22628-2 | doi=10.1007/978-3-030-22629-9_17 | page=232–246|url=https://resources.mpi-inf.mpg.de/keyboardoptimization/MOTOR2019/MOTOR2019.pdf}}</ref>

==See also==

Line 38 ⟶ 50:

== References ==

{{Reflist}}

* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} A2.5: ND43, pg.218.

== Other sources ==

* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A2.5: ND43, pg.218.

==External links==

* httphttps://wwwdoi.seas.upennorg/10.edu7488/qaplibds/3428 QAPLIB - A Quadratic Assignment Problem Library

* http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Java-based Quadratic Assignment Problem Solver

* http://issuu.com/spconguy/docs/ant-algorithm-applied-to-the-quadratic-assignment- - A QAP sample application

* 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

[[Category:NP-hard problems]]

[[Category:Combinatorial optimization]]

[[Category:Operations research]]