Quadratic assignment problem: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
m (Improved citation for Burkard PDF)
 
(85 intermediate revisions by 3 users not shown)
Line 3: Line 3:
== Introduction ==
== Introduction ==


The Quadratic Assignment Problem, discovered by Koopmans and Beckmann in 1957, is a mathematical optimization module created to describe the location of invisible economic activities. An NP Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, Inter-plant Transportation, Hospital Transportation, Exam Scheduling, along with many other applications not described within this page.  
The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957<ref name="Koopmans">Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742</ref>, is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, inter-plant transportation, hospital transportation, exam scheduling, along with many other applications not described within this page.  
== Theory, Methodology, and/or Algorithmic Discussions ==
== Theory, Methodology, and/or Algorithmic Discussions ==


=== Computational Complexity ===
=== Koopmans-Beckman Mathematical Formulation  ===
QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who state that of all combinatorial optimization problems, QAP is the “hardest of the hard”.<ref>Burkard R.E., Çela E., Pardalos P.M., Pitsoulis L.S. (1998) The Quadratic Assignment Problem. In: Du DZ., Pardalos P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-0303-9_27</ref>
Economists Koopmans and Beckman began their investigation of the QAP to ascertain the optimal method of locating important economic resources in a given area. The Koopmans-Beckman formulation of the QAP aims to achieve the objective of assigning facilities to locations in order to minimize the overall cost. Below is the Koopmans-Beckman formulation of the QAP as described by neos-guide.org.


Algorithmic Discussions
=== Quadratic Assignment Problem Formulation  ===


==== Parameters ====
<math>F = (F_{ij})</math> is an n x n matrix where <math>F_{ij}</math> the required flow between facilities <math>i</math> and  <math>j</math>.
<math>D = (D_{ij})</math> is an n x n matrix where <math>D_{ij}</math> the distance between facilities <math>i</math> and  <math>j</math> <math>i</math> and <math>j</math> <ref name="NeosGuide">Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem</ref>. Intuitively, the product of distance and flow represents cost, and the objective  is to minimize this cost. Ideally, two facilities with lots of flow (more product or supplies) between the two should be placed closer together than two facilities that rarely interact (low flow).
==== Sets ====
Consider the set of numbers
<math>N =  \big\{1, 2, ...n\big\}  </math>. 
The group of bijections between <math>N </math> and itself is defined as
<math>S_{n} = \{\phi:  N \rightarrow N \}</math>. Each member <math>\phi \in S_n</math> represents a particular arrangement of the <math>n</math> elements. As an example, the permutation <math>\phi=(3 2 1)</math> represents facility 3 being placed at location 1, facility 1 at location 3 and facility 2 at location 2. Each permutation can be assigned a permutation matrix. The permutation matrix of <math>\phi </math> can be written as <ref name="psu">Burkard, R. E., Çela, E., Pardalos, P. M., &amp; Pitsoulis, L. S. (2013). The Quadratic Assignment Problem. https://www.opt.math.tugraz.at/~cela/papers/qap_bericht.pdf.</ref>
<math>X_{\phi} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 &0 \\ 1 & 0 & 0 \end{bmatrix}</math>
The operation <math>X_{\phi}DX_{\phi}^{T} </math> permutes the values of the distance matrix <math>D</math> so that <math>(X_{\phi}DX_{\phi}^{T})_{i,j} </math> represents the distance between facilities <math>i</math> and <math>j</math> if the facilities are arranged according to the permutation <math>\phi</math>.  The cost function between facilities <math>i</math> and <math>j</math>, after being permuted to their location, is <math>F_{i,j}</math><math>(X_{\phi}DX_{\phi}^{T})_{i,j} </math> <ref name="psu" />. To find the total cost, sum over each <math>i</math> and <math>j</math> for the facilities arranged according to <math>\phi</math>.
=== Inner Product ===
The inner product of two matrices <math>A,B</math> is defined as
<math> \langle A,B \rangle= \sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}b_{i,j}</math>. The inner product
<math>\langle F,X_{\phi}DX_{\phi}^{T} \rangle = \sum_{i=1}^{n}\sum_{j=1}^{n}F_{i,j}(X_{\phi}DX_{\phi}^{T})_{i,j}</math> 
thus describes the total cost of assigning facilities <ref name="psu" /> to locations according to <math>\phi</math>. The objective function to minimize cost can be written as
<math>\langle F,XDX^{T} \rangle </math>.                   
Note: The true objective cost function only requires summing entries above the diagonal in the matrix comprised of elements
<math>F_{i,j}(X_{\phi}DX_{\phi}^{T})_{i,j} </math>.
Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value. See the Numerical Example section for an example of this note.
==== Optimization Problem ====
With all of this information, the QAP can be summarized as:
<math>\min_{X \in P} \langle F,XDX^{T} \rangle </math>.
=== Computational Complexity  ===
QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who states that of all combinatorial optimization problems, QAP is the “hardest of the hard”.<ref name="NeosGuide" />
=== Algorithmic Discussions  ===
While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:
While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:
# Dynamic Program
# Dynamic Program
# Cutting Plane
# Cutting Plane
# Branch and Bound Procedures
# Branch and Bound Procedures
The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.
The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.


== Numerical Example ==
=== Branch and Bound Procedures  ===
The Branch and Bound method was first proposed by Ailsa Land and Alison Doig in 1960 and is the most commonly used tool for solving NP-hard optimization problems.


=== Distance and Flow Matrices ===
A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before one lists all of the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and the branch is eliminated if it cannot produce a better solution than the best one found so far by the algorithm.
For each pair <math>(i,j)</math>,  <math>D_{i,j}</math> represents the distance between locations <math>i</math> and <math>j</math>. <math>F_{i,j}</math> represents the required flow (of supplies, products, etc.) between facilities <math>i</math> and <math>j</math> <ref>https://neos-guide.org/content/quadratic-assignment-problem</ref>. The optimal solution will be the arrangement of the 3 facilities in the 3 locations so that the total flow over distance is minimized. Intuitively, the product of distance and flow represents cost, and the objective  is to minimize this cost. Ideally, two facilities with lots of flow (more product or supplies) between the two should be placed closer together than two facilities that rarely interact (low flow).


=== Permutations ===
=== Linearizations  ===
There are <math>3! = 6</math> permutations of the 3 facilities in the 3 locations. The set of these permutations is typically denoted <math>S_3 </math>. As an example, the permutation <math>\phi=(3 2 1)</math> represents facility 3 being placed at location 1, facility 1 at location 2 and facility 2 at location 3. Each permutation can be assigned a permutation matrix. The permutation matrix of <math>\phi </math> can be written as <ref name="psu">https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf</ref> 
The first attempts to solve the QAP eliminated the quadratic term in the objective function of
   
<math>min \sum_{i=1}^{n}\sum_{j=1}^{n}c{_{\phi(i)\phi(j)}} + \sum_{i=1}^{n}b{_{\phi(i)}}</math>


<math>X_{\phi} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 &0 \\ 0 &1 & 0 \end{bmatrix}</math> 
in order to transform the problem into a (mixed) 0-1 linear program. The objective function is usually linearized by introducing new variables and new linear (and binary) constraints. Then existing methods for (mixed) linear integer programming (MILP) can be applied. The very large number of new variables and constraints, however, usually poses an obstacle for efficiently solving the resulting linear integer programs. MILP formulations provide LP relaxations of the problem which can be used to compute lower bounds.  
 
The operation <math>X_{\phi}DX_{\phi}^{T} </math> permutes the values of the distance matrix <math>D_{i,j}</math> so that <math>(X_{\phi}DX_{\phi}^{T})_{i,j} </math> represents the distance between facilities <math>i</math> and <math>j</math> if the facilities are arranged according to the permutation <math>\phi</math>. The cost function between facilities <math>i</math> and <math>j</math>, after being permuted to their location, is <math>F_{i,j}</math><math>(X_{\phi}DX_{\phi}^{T})_{i,j} </math> <ref name="psu" />. To find the total cost, sum over each <math>i</math> and <math>j</math> for the facilities arranged according to <math>\phi</math>.  
 
=== Inner Product ===
The inner product of two matrices <math>A,B</math> is defined as <math><A,B> = \sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}b_{i,j}</math>. The inner product <math><F,X_{\phi}DX_{\phi}^{T}> = \sum_{i=1}^{n}\sum_{j=1}^{n}F_{i,j}(X_{\phi}DX_{\phi}^{T})_{i,j}</math>  thus describes the total cost of assigning facilities <ref name="psu" /> to locations according to <math>\phi</math>. The objective function to minimize cost can be written as <math><F,XDX^{T}></math>.                    


 
== Numerical Example ==
The true objective cost function only uses the entries above the diagonal in the matrix comprised of elements <math>F_{i,j}</math><math>(X_{\phi}DX_{\phi}^{T})_{i,j} </math>.Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value.


=== QAP with 3 Facilities ===
=== QAP with 3 Facilities ===
Line 44: Line 78:
Let <math>P</math> be the set of permutation matrices for <math>S_3 </math>. The problem can be stated as follows:           
Let <math>P</math> be the set of permutation matrices for <math>S_3 </math>. The problem can be stated as follows:           


<math>\min_{X \in P} <F,XDX^{T}></math>.     
<math>\min_{X \in P} \langle F,XDX^{T} \rangle </math>.     


The table lists the resulting cost function to place the facilities according to each permutation <math>\phi \in S_3 </math>. Note that <math>\phi = () </math> is the identity mapping where the number of the facility is the location number. Based on these results, <math>\phi_4=(13)</math> is the arrangement of facilities that minimizes the cost function with a value of 86.5. Facility 1 should be placed at location 3, Facility 2 remains at location 2 and Facility 3 is placed at location 1.   
The table lists the resulting cost function to place the facilities according to each permutation <math>\phi \in S_3 </math>. Note that <math>\phi = (123) </math> is the identity mapping where the number of the facility matches the location number. Based on these results, <math>\phi_4=(321)</math> is the arrangement of facilities that minimizes the cost function with a value of 86.5. Facility 1 should be placed at location 3, Facility 2 remains at location 2 and Facility 3 is placed at location 1.   
{| class="wikitable sortable"
{| class="wikitable sortable"
|+Cost for Each Permutation in <math>S_3 </math>
|+Cost for Each Permutation in <math>S_3 </math>
Line 52: Line 86:
|Cost
|Cost
|-
|-
|<math>\phi_1=</math> ( )
|<math>\phi_1=</math> (123)
|91.4
|91.4
|-
|-
|<math>\phi_2= (1 2)</math>
|<math>\phi_2= (213)</math>
|99.8
|99.8
|-
|-
|<math>\phi_3=(23)</math>
|<math>\phi_3=(132)</math>
|98.4
|98.4
|-
|-
|<math>\phi_4=(13)</math>
|<math>\phi_4=(321)</math>
|86.5
|86.5
|-
|-
|<math>\phi_5=(123)</math>
|<math>\phi_5=(312)</math>
|103.3
|103.3
|-
|-
|<math>\phi_6=(132)</math>
|<math>\phi_6=(231)</math>
|90
|90
|}   
|}   
For the optimal solution <math>\phi_4=(13)</math>, the calculation is as follows:
<math>XDX^T = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0 & 5 & 6 \\ 5 & 0 & 3.6 \\ 6 & 3.6 & 0 \end{bmatrix}\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 3.6 & 6 \\ 3.6 & 0 & 5 \\ 6 & 5 & 0 \end{bmatrix}
</math>
<math>
F_{i,j}(X_{\phi}DX_{\phi}^{T})_{i,j} =
\begin{bmatrix} 0 & 36 & 18 \\ 36 & 0 & 32.5\\ 18 & 32.5 & 0 \end{bmatrix}
</math>
Looking at the figure of the optimal solution, the flow<math>\times</math>distance values are repeated in this matrix which is why the sum of all elements must be divided by 2. This gives <math> \langle F,X_{\phi}DX_{\phi}^{T} \rangle  = 173</math> so the minimum cost is 86.5.


[[File:OptimalSolution2.jpg|none|thumb|400x400px|Optimal Solution for the example with facility/location pairings listed.  Line thickness is representative of flow. Note that the closest locations (2,3) are assigned facilities (2,1) with the greatest flow between them. The two farthest locations (1,3) are assigned facilities (3,1) that have the lowest flow. Overall, this results in a minimized cost function.]]
[[File:OptimalSolution2.jpg|none|thumb|400x400px|Optimal Solution for the example with facility/location pairings listed.  Line thickness is representative of flow. Note that the closest locations (2,3) are assigned facilities (2,1) with the greatest flow between them. The two farthest locations (1,3) are assigned facilities (3,1) that have the lowest flow. Overall, this results in a minimized cost function.]]
Line 76: Line 124:


=== Inter-plant Transportation Problem ===
=== Inter-plant Transportation Problem ===
The quadratic assignment problem was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations.<ref>Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742</ref> Factoring in the location of the each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.
The QAP was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations.<ref name="Koopmans" /> Factoring in the location of each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.


=== The Backboard Wiring Problem ===
=== The Backboard Wiring Problem ===
As the quadratic assignment problem is focused on minimizing the cost of traveling from one location to another, it is an ideal approach determining placement of components in many modern electronics. Leon Steinberg proposed a QAP solution optimize the layout of elements on a blackboard by minimizing the total amount of wiring required.<ref>Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. ''SIAM Review''. 1961;3(1):37.</ref>  
As the QAP is focused on minimizing the cost of traveling from one location to another, it is an ideal approach to determining the placement of components in many modern electronics. Leon Steinberg proposed a QAP solution to optimize the layout of elements on a blackboard by minimizing the total amount of wiring required.<ref name="Steinberg">Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. ''SIAM Review''. 1961;3(1):37.</ref>  


When defining the problem Steinberg states that we have a set of n elements  
When defining the problem Steinberg states that we have a set of n elements  
Line 102: Line 150:
<math>s(x)</math> represents a particular placement of a component.
<math>s(x)</math> represents a particular placement of a component.


In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.  
In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation, he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.  


The initial placement of components is shown below:
The initial placement of components is shown below:
[[File:Initial wire length.jpg|center|thumb|412x412px|The initial placement of components in the backboard from Steinberg's ]]
[[File:Initial wire length.jpg|center|thumb|412x412px|The initial placement of components in the backboard from Steinberg's ]]
After the initial placement of elements it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.
After the initial placement of elements, it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.
[[File:Final wire length.jpg|center|thumb|377x377px|Final component position in Steinberg's Backboard optimization problem]]
[[File:Final wire length.jpg|center|thumb|377x377px|Final component position in Steinberg's Backboard optimization problem]]


=== Hospital Layout ===
=== Hospital Layout ===
Building a new hospitals was a common event in  1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem".<ref>Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. ''Operational Research Quarterly (1970-1977)''. 1977;28(1):167. doi:10.2307/300878</ref>With high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create a optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Out-patient ward was acting as a bottle neck in the hospital and focused his efforts on optimizing the 17 departments there.
Building new hospitals was a common event in  1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem".<ref name="Elshafei">Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. ''Operational Research Quarterly (1970-1977)''. 1977;28(1):167. doi:10.2307/300878</ref>With the high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create an optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Outpatient ward was acting as a bottleneck in the hospital and focused his efforts on optimizing the 17 departments there.




Line 121: Line 169:
<math>\sum_{i \epsilon I }y_{ij} = 1 \forall j \epsilon J </math>
<math>\sum_{i \epsilon I }y_{ij} = 1 \forall j \epsilon J </math>


<math>y_{ij}\begin{Bmatrix}1 if facility i is located at j
<math>y_{ij} = \begin{Bmatrix} 1 \mbox{, if facility i is located at j}
\\ 0 otherwise
\\ 0\mbox{, otherwise}


\end{Bmatrix} </math>
\end{Bmatrix} </math>
Line 136: Line 184:




It can take a large amount of computational power to calculate the solution to a QAP problem, necessitating the use of a heuristic solution rather than using an optimizing algorithm. This approach is composed of two parts(Parts A and Part B). Part A that develops the initial layout of the hospital, this is done by following two strategies. Strategy 1 where we use a rank <math>L_{i} </math> that designates the number of interactions facility <math>i </math> has with with the other facilities. As well as ranking them in terms of <math>R_{j} </math>, which designates the sum of distances from j to all other locations. then we go through the list and find the facility with the greatest <math>L_{i} </math> and the least <math>R_{j} </math>. Strategy 2 says that any step in the process we next place an unassigned facility that has the largest number of interactions with the most recently placed facility. Part B covers improving the initial solution developed in Part A, here at any step in the process we test weather the assignment is best of all of the facilities that are involved and make swaps where necessary until there are no more swaps to be made.  
It can take a large amount of computational power to calculate the solution to a QAP problem, necessitating the use of a heuristic solution rather than using an optimizing algorithm. This approach is composed of two parts(Parts A and Part B). Part A develops the initial layout of the hospital, this is done by the following two strategies. Strategy 1 where we use a rank <math>L_{i} </math> that designates the number of interactions facility <math>i </math> has with with the other facilities. As well as ranking them in terms of <math>R_{j} </math>, which designates the sum of distances from j to all other locations. then we go through the list and find the facility with the greatest <math>L_{i} </math> and the least <math>R_{j} </math>. Strategy 2 says that at any step in the process we next place an unassigned facility that has the largest number of interactions with the most recently placed facility. Part B covers improving the initial solution developed in Part A, here at any step in the process we test whether the assignment is best for all of the facilities that are involved and make swaps where necessary until there are no more swaps to be made.  


For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 biased on the original hospital layout.  
For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 based on the original hospital layout.


=== Exam Scheduling System ===
=== Exam Scheduling System ===
The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.”<ref>Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.</ref>
The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross-program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.”<ref name="Muktar">Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.</ref>


== Conclusion ==
== Conclusion ==


Optimization of the QAP is easily stated but requires significant computational power. The number of potential facility/location combinations grows as <math>n!</math>. Thus for a QAP of just <math> n=6 </math> facilities and location, there are <math>720</math> facility/location pairings. The QAP can be used in applications beyond just the location of economic activities that it was originally developed for by Koopmans and Beckmann.<ref name="Koopmans" /> The QAP has been used to optimize backboard wiring <ref name="Steinberg" />, hospital layouts <ref name="Elshafei" />, and to schedule exams <ref name="Muktar" />, along with other applications not defined on this page.


== References ==
== References ==
<references />

Latest revision as of 00:51, 14 December 2020

Author: Thomas Kueny, Eric Miller, Natasha Rice, Joseph Szczerba, David Wittmann (SysEn 5800 Fall 2020)

Introduction

The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957[1], is a mathematical optimization module created to describe the location of invisible economic activities. An NP-Complete problem, this model can be applied to many other optimization problems outside of the field of economics. It has been used to optimize backboards, inter-plant transportation, hospital transportation, exam scheduling, along with many other applications not described within this page.

Theory, Methodology, and/or Algorithmic Discussions

Koopmans-Beckman Mathematical Formulation

Economists Koopmans and Beckman began their investigation of the QAP to ascertain the optimal method of locating important economic resources in a given area. The Koopmans-Beckman formulation of the QAP aims to achieve the objective of assigning facilities to locations in order to minimize the overall cost. Below is the Koopmans-Beckman formulation of the QAP as described by neos-guide.org.

Quadratic Assignment Problem Formulation

Parameters

is an n x n matrix where the required flow between facilities and . is an n x n matrix where the distance between facilities and and [2]. Intuitively, the product of distance and flow represents cost, and the objective is to minimize this cost. Ideally, two facilities with lots of flow (more product or supplies) between the two should be placed closer together than two facilities that rarely interact (low flow).

Sets

Consider the set of numbers . The group of bijections between and itself is defined as . Each member represents a particular arrangement of the elements. As an example, the permutation represents facility 3 being placed at location 1, facility 1 at location 3 and facility 2 at location 2. Each permutation can be assigned a permutation matrix. The permutation matrix of can be written as [3]


The operation permutes the values of the distance matrix so that represents the distance between facilities and if the facilities are arranged according to the permutation . The cost function between facilities and , after being permuted to their location, is [3]. To find the total cost, sum over each and for the facilities arranged according to .

Inner Product

The inner product of two matrices is defined as . The inner product

thus describes the total cost of assigning facilities [3] to locations according to . The objective function to minimize cost can be written as

.

Note: The true objective cost function only requires summing entries above the diagonal in the matrix comprised of elements

.

Since this matrix is symmetric with zeroes on the diagonal, dividing by 2 removes the double count of each element to give the correct cost value. See the Numerical Example section for an example of this note.

Optimization Problem

With all of this information, the QAP can be summarized as:

.

Computational Complexity

QAP belongs to the classification of problems known as NP-complete, thus being a computationally complex problem. QAP’s NP-completeness was proven by Sahni and Gonzalez in 1976, who states that of all combinatorial optimization problems, QAP is the “hardest of the hard”.[2]

Algorithmic Discussions

While an algorithm that can solve QAP in polynomial time is unlikely to exist, there are three primary methods for acquiring the optimal solution to a QAP problem:

  1. Dynamic Program
  2. Cutting Plane
  3. Branch and Bound Procedures

The third method has been proven to be the most effective in solving QAP, although when n > 15, QAP begins to become virtually unsolvable.

Branch and Bound Procedures

The Branch and Bound method was first proposed by Ailsa Land and Alison Doig in 1960 and is the most commonly used tool for solving NP-hard optimization problems.

A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before one lists all of the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and the branch is eliminated if it cannot produce a better solution than the best one found so far by the algorithm.

Linearizations

The first attempts to solve the QAP eliminated the quadratic term in the objective function of

in order to transform the problem into a (mixed) 0-1 linear program. The objective function is usually linearized by introducing new variables and new linear (and binary) constraints. Then existing methods for (mixed) linear integer programming (MILP) can be applied. The very large number of new variables and constraints, however, usually poses an obstacle for efficiently solving the resulting linear integer programs. MILP formulations provide LP relaxations of the problem which can be used to compute lower bounds.

Numerical Example

QAP with 3 Facilities

Consider the QAP of placing 3 facilities in 3 locations. Let the distance and flow matrices be defined respectively as , .

Let be the set of permutation matrices for . The problem can be stated as follows:

.

The table lists the resulting cost function to place the facilities according to each permutation . Note that is the identity mapping where the number of the facility matches the location number. Based on these results, is the arrangement of facilities that minimizes the cost function with a value of 86.5. Facility 1 should be placed at location 3, Facility 2 remains at location 2 and Facility 3 is placed at location 1.

Cost for Each Permutation in
Permutation Cost
(123) 91.4
99.8
98.4
86.5
103.3
90


For the optimal solution , the calculation is as follows:


Looking at the figure of the optimal solution, the flowdistance values are repeated in this matrix which is why the sum of all elements must be divided by 2. This gives so the minimum cost is 86.5.

Optimal Solution for the example with facility/location pairings listed. Line thickness is representative of flow. Note that the closest locations (2,3) are assigned facilities (2,1) with the greatest flow between them. The two farthest locations (1,3) are assigned facilities (3,1) that have the lowest flow. Overall, this results in a minimized cost function.

Applications

Inter-plant Transportation Problem

The QAP was first introduced by Koopmans and Beckmann to address how economic decisions could be made to optimize the transportation costs of goods between both manufacturing plants and locations.[1] Factoring in the location of each of the manufacturing plants as well as the volume of goods between locations to maximize revenue is what distinguishes this from other linear programming assignment problems like the Knapsack Problem.

The Backboard Wiring Problem

As the QAP is focused on minimizing the cost of traveling from one location to another, it is an ideal approach to determining the placement of components in many modern electronics. Leon Steinberg proposed a QAP solution to optimize the layout of elements on a blackboard by minimizing the total amount of wiring required.[4]

When defining the problem Steinberg states that we have a set of n elements

as well as a set of r points

where

In his paper he derives the below formula:


represents the number of wires connecting components and

is the length of wire needed to connect tow components if one is placed at and the other is placed at . If has coordinates then can be calculated by

represents a particular placement of a component.

In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard. For the calculation, he selected a random initial placement of s1 and chose a random family of 25 unconnected sets.

The initial placement of components is shown below:

The initial placement of components in the backboard from Steinberg's

After the initial placement of elements, it took an additional 35 iterations to get us to our final optimized backboard layout. Leading to a total of 59 iterations and a final wire length of 4,969.440.

Final component position in Steinberg's Backboard optimization problem

Hospital Layout

Building new hospitals was a common event in 1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem".[5]With the high initial cost to construct the hospital and to staff it, it is important to ensure that it is operating as efficiently as possible. Elshafei's paper was commissioned to create an optimization formula to locate clinics within a building in such a way that minimizes the total distance that a patient travels within the hospital throughout the year. When doing a study of a major hospital in Cairo he determined that the Outpatient ward was acting as a bottleneck in the hospital and focused his efforts on optimizing the 17 departments there.


Elshafei identified the following QAP to determine where clinics should be placed:

Such that

is the yearly flow between facilities i and k

is the distance between the possible facility locations j and q

is the initial set of facilities

is the initial set of all locations


It can take a large amount of computational power to calculate the solution to a QAP problem, necessitating the use of a heuristic solution rather than using an optimizing algorithm. This approach is composed of two parts(Parts A and Part B). Part A develops the initial layout of the hospital, this is done by the following two strategies. Strategy 1 where we use a rank that designates the number of interactions facility has with with the other facilities. As well as ranking them in terms of , which designates the sum of distances from j to all other locations. then we go through the list and find the facility with the greatest and the least . Strategy 2 says that at any step in the process we next place an unassigned facility that has the largest number of interactions with the most recently placed facility. Part B covers improving the initial solution developed in Part A, here at any step in the process we test whether the assignment is best for all of the facilities that are involved and make swaps where necessary until there are no more swaps to be made.

For the Cairo hospital with 17 clinics, and one receiving and recording room bringing us to a total of 18 facilities. By running the above optimization Elshafei was able to get the total distance per year down to 11,281,887 from a distance of 13,973,298 based on the original hospital layout.

Exam Scheduling System

The scheduling system uses matrices for Exams, Time Slots, and Rooms with the goal of reducing the rate of schedule conflicts. To accomplish this goal, the “examination with the highest cross faculty student is been prioritized in the schedule after which the examination with the highest number of cross-program is considered and finally with the highest number of repeating student, at each stage group with the highest number of student are prioritized.”[6]

Conclusion

Optimization of the QAP is easily stated but requires significant computational power. The number of potential facility/location combinations grows as . Thus for a QAP of just facilities and location, there are facility/location pairings. The QAP can be used in applications beyond just the location of economic activities that it was originally developed for by Koopmans and Beckmann.[1] The QAP has been used to optimize backboard wiring [4], hospital layouts [5], and to schedule exams [6], along with other applications not defined on this page.

References

  1. 1.0 1.1 1.2 Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
  2. 2.0 2.1 Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem
  3. 3.0 3.1 3.2 Burkard, R. E., Çela, E., Pardalos, P. M., & Pitsoulis, L. S. (2013). The Quadratic Assignment Problem. https://www.opt.math.tugraz.at/~cela/papers/qap_bericht.pdf.
  4. 4.0 4.1 Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review. 1961;3(1):37.
  5. 5.0 5.1 Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977). 1977;28(1):167. doi:10.2307/300878
  6. 6.0 6.1 Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.