Quadratic assignment problem - Revision history

DavidWittmann: Improved citation for Burkard PDF

2020-12-14T04:51:35Z

Improved citation for Burkard PDF

← Older revision		Revision as of 00:51, 14 December 2020
Line 19:		Line 19:
	<math>N = \big\{1, 2, ...n\big\} </math>.		<math>N = \big\{1, 2, ...n\big\} </math>.
	The group of bijections between <math>N </math> and itself is defined as		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">https://~~citeseerx~~.~~ist~~.~~psu~~.~~edu~~/~~viewdoc~~/~~download?doi=10~~.1.~~1.217.1914&rep=rep1&type=pdf~~</ref>		<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., & 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>		<math>X_{\phi} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 &0 \\ 1 & 0 & 0 \end{bmatrix}</math>

DavidWittmann: /* Conclusion */ Grammar fix

2020-12-14T01:28:55Z

Conclusion: Grammar fix

← Older revision		Revision as of 21:28, 13 December 2020
Line 193:		Line 193:
	== 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 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.		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 ==

DavidWittmann: Added repeated citations for the rest of the references with broken formatting.

2020-12-14T01:26:47Z

Added repeated citations for the rest of the references with broken formatting.

← Older revision		Revision as of 21:26, 13 December 2020
Line 13:		Line 13:
	==== Parameters ====		==== 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>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>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).		<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 ====		==== Sets ====
Line 48:		Line 48:

	=== Computational Complexity ===		=== 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”.~~[1]~~		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 ===		=== Algorithmic Discussions ===
Line 127:		Line 127:

	=== The Backboard Wiring 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.<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 158:		Line 158:

	=== Hospital Layout ===		=== 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".<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 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.		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 189:		Line 189:

	=== 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 ~~[3]~~. 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.		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 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 ==

DavidWittmann: Added first repeated citation to fix reference formatting. Need to verify results of reference.

2020-12-14T01:02:02Z

Added first repeated citation to fix reference formatting. Need to verify results of reference.

← Older revision		Revision as of 21:02, 13 December 2020
Line 3:		Line 3:
	== Introduction ==		== Introduction ==

	The Quadratic Assignment Problem (QAP), discovered by Koopmans and Beckmann in 1957~~[3]~~, 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 ==

Line 124:		Line 124:

	=== Inter-plant Transportation Problem ===		=== 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.<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 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 ===

NatashaRice at 22:15, 13 December 2020

2020-12-13T22:15:27Z

← Older revision		Revision as of 18:15, 13 December 2020
Line 194:		Line 194:

	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 [3]. 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.		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 [3]. 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.

	~~SUMMARIZE THEORY~~

	== References ==		== References ==

NatashaRice at 22:14, 13 December 2020

2020-12-13T22:14:55Z

← Older revision		Revision as of 18:14, 13 December 2020
Line 196:		Line 196:

	SUMMARIZE THEORY		SUMMARIZE THEORY

			== References ==

NatashaRice: /* References */

2020-12-13T22:00:08Z

References

← Older revision		Revision as of 18:00, 13 December 2020
Line 195:		Line 195:
	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 [3]. 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.		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 [3]. 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.

	SUMMARIZE THEORY		SUMMARIZE THEORY



	~~== References ==~~
	~~https://neos-guide.org/content/quadratic-assignment-problem~~
	~~https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf~~
	~~Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742~~
	~~Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review. 1961;3(1):37.~~
	~~Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977). 1977;28(1):167. doi:10.2307/300878~~
	~~Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.~~
	~~Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742~~
	~~<references />~~

NatashaRice at 21:59, 13 December 2020

2020-12-13T21:59:42Z

← Older revision		Revision as of 17:59, 13 December 2020
Line 3:		Line 3:
	== Introduction ==		== Introduction ==

	The Quadratic Assignment Problem (QAP), 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[3], 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 ==

Line 193:		Line 193:
	== Conclusion ==		== Conclusion ==

	Optimization of the QAP ~~problem~~ 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.		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 [3]. 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.

	SUMMARIZE THEORY		SUMMARIZE THEORY


	~~SUMMARIZE APPLICATIONS~~

	== References ==		== References ==

NatashaRice: /* References */

2020-12-07T06:51:09Z

References

← Older revision		Revision as of 02:51, 7 December 2020
Line 201:		Line 201:

	== References ==		== References ==

	~~<references />~~
	https://neos-guide.org/content/quadratic-assignment-problem		https://neos-guide.org/content/quadratic-assignment-problem
	https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf		https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf
Line 210:		Line 208:
	Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.		Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.
	Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742		Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
			<references />

NatashaRice: /* References */

2020-12-07T06:50:46Z

References

← Older revision		Revision as of 02:50, 7 December 2020
Line 203:		Line 203:

	<references />		<references />
			https://neos-guide.org/content/quadratic-assignment-problem
			https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.217.1914&rep=rep1&type=pdf
			Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742
			Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review. 1961;3(1):37.
			Alwalid N. Elshafei. Hospital Layout as a Quadratic Assignment Problem. Operational Research Quarterly (1970-1977). 1977;28(1):167. doi:10.2307/300878
			Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.
			Koopmans, T., & Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25(1), 53-76. doi:10.2307/1907742