Quadratic assignment problem

<h2 id="formal-mathematical-definition">Formal mathematical definition</h2>

<p>The formal definition of the quadratic assignment problem is as follows:
</p>
Given two sets, <i>P</i> ("facilities") and <i>L</i> ("locations"), of equal size, together with a <a href="/facts/Weight_function/YNJL7o99">weight function</a> <i>w</i> : <i>P</i> × <i>P</i> → <a href="/facts/Real_number/R02gw5Pb">R</a> and a distance function <i>d</i> : <i>L</i> × <i>L</i> → <a href="/facts/Real_number/R02gw5Pb">R</a>. Find the <a href="/facts/Bijection/j4gTuTmW">bijection</a> <i>f</i> : <i>P</i> → <i>L</i> ("assignment") such that the cost function:

∑
          
            a
            ,
            b
            ∈
            P
          
        
        w
        (
        a
        ,
        b
        )
        ⋅
        d
        (
        f
        (
        a
        )
        ,
        f
        (
        b
        )
        )
      
    
    {\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))}

is minimized.
<p>Usually  weight and distance functions are viewed as square real-valued <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrices</a>, so that the cost function is written down as:
</p>

∑
          
            a
            ,
            b
            ∈
            P
          
        
        
          w
          
            a
            ,
            b
          
        
        
          d
          
            f
            (
            a
            )
            ,
            f
            (
            b
            )
          
        
      
    
    {\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}

<p>In matrix notation:
</p>

min
          
            X
            ∈
            
              Π
              
                n
              
            
          
        
        trace
        ⁡
        (
        W
        X
        
          D
          
            T
          
        
        
          X
          
            T
          
        
        )
      
    
    {\displaystyle \min _{X\in \Pi _{n}}\operatorname {trace} (WXD^{T}X^{T})}

<p>where 
  
    
      
        
          Π
          
            n
          
        
      
    
    {\displaystyle \Pi _{n}}
  
 is the set of 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 permutation matrices, 
  
    
      
        W
      
    
    {\displaystyle W}
  
 is the weight matrix and 
  
    
      
        D
      
    
    {\displaystyle D}
  
 is the distance matrix.
</p>
<h2 id="computational-complexity">Computational complexity</h2>
<p>The problem is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, so there is no known <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> 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.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> The <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a> (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 <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problems may be written in this form.
</p>
<h2 id="applications">Applications</h2>
<p>In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected <a href="/facts/Electronic_component/F3NBVv4Q">electronic components</a> onto a <a href="/facts/Printed_circuit_board/muSR2p43">printed circuit board</a> or on a <a href="/facts/Integrated_circuit/fjn6vg7C">microchip</a>, which is part of the <a href="/facts/Place_and_route/UJgLLNdP">place and route</a> stage of <a href="/facts/Computer_aided_design/5gSXrmmN">computer aided design</a> in the electronics industry.
</p><p>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).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Quadratic_bottleneck_assignment_problem/eTyu7FgL">Quadratic bottleneck assignment problem</a></li></ul>

<h2 id="other-sources">Other sources</h2>
<ul><li><a href="/facts/Michael_R._Garey/xuSLYs90">Michael R. Garey</a> and <a href="/facts/David_S._Johnson/kGSBxucb">David S. Johnson</a> (1979). <a href="/facts/Computers_and_Intractability%3a_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss"><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i></a>. W.H. Freeman. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-7167-1045-5. A2.5: ND43, pg.218.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://doi.org/10.7488/ds/3428">https://doi.org/10.7488/ds/3428</a> QAPLIB - A Quadratic Assignment Problem Library</li>
<li><a href="http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/">http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/</a>  MAOS-QAP - Java-based Quadratic Assignment Problem Solver</li>
<li><a href="https://CRAN.R-project.org/package=qap">https://CRAN.R-project.org/package=qap</a> - R package qap: Heuristics for the Quadratic Assignment Problem</li>
<li><a href="https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ">https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ</a> - Metaheuristic QAP solver for Windows 10/11</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Sahni, Sartaj; Gonzalez, Teofilo (July 1976). "P-Complete Approximation Problems". Journal of the ACM. 23 (3): 555–565. doi:10.1145/321958.321975. hdl:10338.dmlcz/103883. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>John, Maximilian; Karrenbauer, Andreas (2019). "Dynamic Sparsification for Quadratic Assignment Problems". Mathematical Optimization Theory and Operations Research (PDF). Vol. 11548. Cham: Springer International Publishing. p. 232–246. doi:10.1007/978-3-030-22629-9_17. ISBN 978-3-030-22628-2. <a href="978-3-030-22628-2" target="_blank">978-3-030-22628-2</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Quadratic assignment problem open-in-new

Quadratic assignment problem