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.

Example

Eric Miller to provide.

Applications

Natasha Rice and David Wittmann to provide.

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:

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_{1\leq i \leq j \leq n }^{} C_{ij}(d_{s(i)s(j))}) ^{k}}

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 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 $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 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_{\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}) }

or

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 k} represents

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.

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

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. Phillips AT, Rosen JB. A quadratic assignment formulation of the molecular conformation problem. Journal of Global Optimization: An International Journal Dealing with Theoretical and Computational Aspects of Seeking Global Optima and Their Applications in Science, Management, and Engineer. 1994;4(2):229. doi:10.1007/bf01096724