Quadratic assignment problem

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

Theory, Methodology, and/or Algorithmic Discussions

Joe Szczerba and Tom Kueny to provide.

Numerical Example

Consider the QAP of placing 3 facilities in 3 locations. Let the distance and flow matrices be defined respectively as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D=\begin{bmatrix} 0 & 5 & 6 \\ 5 & 0 & 3.6 \\ 6 & 3.6 & 0 \end{bmatrix} } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle F=\begin{bmatrix} 0 & 10 & 3 \\ 10 & 0 & 6.5\\ 3 & 6.5 & 0 \end{bmatrix} } .

For each pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_{i,j}} represents the distance between locations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} . Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{i,j}} represents the required flow (of supplies, products, etc.) between facilities Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} . 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).

There are $3!=6$ permutations of the 3 facilities in the 3 locations. The set of these permutations is typically denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_3 } . As an example, the permutation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi=(3 2 1)} 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 $\phi$ can be written as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{\phi} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 &0 \\ 0 &1 & 0 \end{bmatrix}} . The operation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_{\phi}DX_{\phi}^{T} } permutes the distance matrix values so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (X_{\phi}DX_{\phi}^{T})_{i,j} } represents the distance between facilities Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} if the facilities are arranged according to the permutation $\phi$. Then the cost function between facilities Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} , after being permuted to their location, is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_{i,j}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (X_{\phi}DX_{\phi}^{T})_{i,j} }

Let $P$ be the set of permutation matrices for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_3 } .The problem can be stated as follows:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min_{X \in P} <F,XDX^{T}>}

Applications

Natasha Rice and David Wittmann to provide.

Inter-plant Transportation Problem

David (Work-in-progress) 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.

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.

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \left \{ E_{1}, E_{2}, ... , E_{n}\right \}}

as well as a set of r points

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{1}, P_{2}, ... , P_{r}} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \geq n}

In his paper he derives the below formula:

$min\sum _{1\leq i\leq j\leq n}^{}C_{ij}(d_{s(i)s(j))})$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{ij}} represents the number of wires connecting components Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{i}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{i}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{s(i)s(j))}} is the length of wire needed to connect tow components if one is placed at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\alpha}} and the other is placed at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\beta}} . If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{\alpha}} has coordinates $(x_{\alpha },y_{\alpha },z_{\alpha })$ then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{s(i)s(j))}} can be calculated by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{s(i)s(j))} = \surd(\bigl(x_{\alpha} - x_{\beta}\bigr)^{2} + \bigl(y_{\alpha} - y_{\beta}\bigr)^{2} + \bigl(z_{\alpha} - z_{\beta}\bigr)^{2}) }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s(x)} 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 a new hospitals was a common event in 1977 when Alealid N Elshafei wrote his paper on "Hospital Layouts as a Quadratic Assignment Problem". 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 Cario 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.

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min \sum_{i,j } \sum_{k,q } f_{ik}d_{jq}y_{ij}y_{kq} }

Such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j \epsilon J }y_{ij} = 1 \forall i \epsilon I }

$\sum _{i\epsilon I}y_{ij}=1\forall j\epsilon J$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}\begin{Bmatrix}1 if facility i is located at j \\ 0 otherwise \end{Bmatrix} }

References

1. Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977). 1977;28(1):167. doi:10.2307/3008789
2. Dickey JW, Hopkins JW. Campus building arrangement using topaz. Transportation Research. 6(1):59-68. doi:10.1016/0041-1647(72)90111-6
3. Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review. 1961;3(1):37.
4. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf
5. Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742