Quadratic assignment problem

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

  • 1 Introduction
  • 2.1 Koopmans-Beckman Mathematical Formulation
  • 2.2.1 Parameters
  • 2.3.1 Optimization Problem
  • 2.4 Computational Complexity
  • 2.5 Algorithmic Discussions
  • 2.6 Branch and Bound Procedures
  • 2.7 Linearizations
  • 3.1 QAP with 3 Facilities
  • 4.1 Inter-plant Transportation Problem
  • 4.2 The Backboard Wiring Problem
  • 4.3 Hospital Layout
  • 4.4 Exam Scheduling System
  • 5 Conclusion
  • 6 References

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

{\displaystyle F=(F_{ij})}

Inner Product

{\displaystyle A,B}

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

{\displaystyle F_{i,j}(X_{\phi }DX_{\phi }^{T})_{i,j}}

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:

{\displaystyle \min _{X\in P}\langle F,XDX^{T}\rangle }

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:

  • Dynamic Program
  • Cutting Plane

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 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

{\displaystyle min\sum _{i=1}^{n}\sum _{j=1}^{n}c{_{\phi (i)\phi (j)}}+\sum _{i=1}^{n}b{_{\phi (i)}}}

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.

{\displaystyle D={\begin{bmatrix}0&5&6\\5&0&3.6\\6&3.6&0\end{bmatrix}}}

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

{\displaystyle E=\left\{E_{1},E_{2},...,E_{n}\right\}}

as well as a set of r points

{\displaystyle P_{1},P_{2},...,P_{r}}

In his paper he derives the below formula:

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

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:

quadratic assignment problem applications

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.

quadratic assignment problem applications

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:

{\displaystyle min\sum _{i,j}\sum _{k,q}f_{ik}d_{jq}y_{ij}y_{kq}}

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]

{\displaystyle n!}

  • ↑ 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.0 2.1 Quadratic Assignment Problem. (2020). Retrieved December 14, 2020, from https://neos-guide.org/content/quadratic-assignment-problem
  • ↑ 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.0 4.1 Leon Steinberg. The Backboard Wiring Problem: A Placement Algorithm. SIAM Review . 1961;3(1):37.
  • ↑ 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.0 6.1 Muktar, D., & Ahmad, Z.M. (2014). Examination Scheduling System Based On Quadratic Assignment.

Navigation menu

  • Analysis of Algorithms
  • Backtracking
  • Dynamic Programming
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Pattern Searching
  • Bitwise Algorithms
  • Branch & Bound
  • Randomized Algorithms

Related Articles

  • Solve Coding Problems
  • Introduction to Exact Cover Problem and Algorithm X
  • Implementation of Exact Cover Problem and Algorithm X using DLX
  • Introduction to Grover's Algorithm
  • Art Gallery Problem
  • Preemptive Priority CPU Scheduling Algorithm
  • Transform and Conquer Technique
  • Representation Change in Transform and Conquer Technique
  • What Does Big O(N^2) Complexity Mean?
  • Algorithm definition and meaning
  • How to write a Pseudo Code?
  • How to develop an Algorithm from Scratch | Develop Algorithmic Thinking
  • Approximation Algorithms
  • Accounting Method | Amortized Analysis
  • Genetic Algorithms
  • Difference between average case and amortized analysis
  • Polynomial Time Approximation Scheme
  • Josephus Problem when k is 2
  • Minimum number of items to be delivered
  • How to store the data for multiple objectives in Shortest path search Algorithms ?

Quadratic Assignment Problem (QAP)

The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them.

The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.

The distance matrix and flow matrix, as well as restrictions to ensure each facility is assigned to exactly one location and each location is assigned to exactly one facility, can be used to formulate the QAP as a quadratic objective function.

The QAP is a well-known example of an NP-hard problem , which means that for larger cases, computing the best solution might be difficult. As a result, many algorithms and heuristics have been created to quickly identify approximations of answers.

There are various types of algorithms for different problem structures, such as:

  • Precise algorithms
  • Approximation algorithms
  • Metaheuristics like genetic algorithms and simulated annealing
  • Specialized algorithms

Example: Given four facilities (F1, F2, F3, F4) and four locations (L1, L2, L3, L4). We have a cost matrix that represents the pairwise distances or costs between facilities. Additionally, we have a flow matrix that represents the interaction or flow between locations. Find the assignment that minimizes the total cost based on the interactions between facilities and locations. Each facility must be assigned to exactly one location, and each location can only accommodate one facility.

Facilities cost matrix:

Flow matrix:

To solve the QAP, various optimization techniques can be used, such as mathematical programming, heuristics, or metaheuristics. These techniques aim to explore the search space and find the optimal or near-optimal solution.

The solution to the QAP will provide an assignment of facilities to locations that minimizes the overall cost.

The solution generates all possible permutations of the assignment and calculates the total cost for each assignment. The optimal assignment is the one that results in the minimum total cost.

To calculate the total cost, we look at each pair of facilities in (i, j) and their respective locations (location1, location2). We then multiply the cost of assigning facility1 to facility2 (facilities[facility1][facility2]) with the flow from location1 to location2 (locations[location1][location2]). This process is done for all pairs of facilities in the assignment, and the costs are summed up.

Overall, the output tells us that assigning facilities to locations as F1->L1, F3->L2, F2->L3, and F4->L4 results in the minimum total cost of 44. This means that Facility 1 is assigned to Location 1, Facility 3 is assigned to Location 2, Facility 2 is assigned to Location 3, and Facility 4 is assigned to Location 4, yielding the lowest cost based on the given cost and flow matrices.This example demonstrates the process of finding the optimal assignment by considering the costs and flows associated with each facility and location. The objective is to find the assignment that minimizes the total cost, taking into account the interactions between facilities and locations.

Applications of the QAP include facility location, logistics, scheduling, and network architecture, all of which require effective resource allocation and arrangement.

Please Login to comment...

  • nikhilgarg527
  • kake_karthik

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

A proximal DC approach for quadratic assignment problem

  • Published: 02 January 2021
  • Volume 78 , pages 825–851, ( 2021 )

Cite this article

  • Zhuoxuan Jiang 1 ,
  • Xinyuan Zhao 1 &
  • Chao Ding   ORCID: orcid.org/0000-0002-4228-6700 2  

453 Accesses

3 Citations

Explore all metrics

In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the difference of convex functions (DC) approach, a semi-proximal DC algorithm is proposed for solving the relaxation of the rank constrained DNN problem whose subproblems can be solved by the semi-proximal augmented Lagrangian method. We show that the generated sequence converges to a stationary point of the corresponding DC problem, which is feasible to the rank constrained DNN problem under some suitable assumptions. Moreover, numerical experiments demonstrate that for most QAP instances, the proposed approach can find the global optimal solutions efficiently, and for others, the proposed algorithm is able to provide good feasible solutions in a reasonable time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

quadratic assignment problem applications

An, L.T.H., Tao, P.D.: DC programming and DCA: thirty years of developments. Math. Program. 169 , 5–68 (2018)

Article   MathSciNet   MATH   Google Scholar  

An, L.T.H., Tao, P.D., Huynh, V.N.: Exact penalty and error bounds in DC programming. J. Global Optim. 52 , 509–535 (2012)

Anstreicher, K.: Recent advances in the solution of quadratic assignment problems. Math. Program. 97 , 27–42 (2003)

Anstreicher, K., Wolkowicz, H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22 , 41–55 (2000)

Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116 , 5–16 (2009)

Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality. Math. Oper. Res. 35 , 438–457 (2010)

Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications, vol. 2. Society for Industrial Mathematics, Philadelphia (2001)

Book   MATH   Google Scholar  

Bi, S.J., Pan, S.H.: Error bounds for rank constrained optimization problems and applications. Oper. Res. Lett. 44 , 336–341 (2016)

Bolte, J., Daniilidis, A., Lewis, A.S.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17 , 1205–1223 (2007)

Article   MATH   Google Scholar  

Bolte, J., Daniilidis, A., Lewis, A.S., Shiota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18 , 556–572 (2007)

Bolte, J., Pauwels, E.: Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs. Math. Oper. Res. 41 , 442–465 (2016)

Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146 , 459–494 (2014)

Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 , 479–495 (2009)

Burkard, P.: Quadratic assignment problems. In: Pardalos, P.M., Du, D.Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 2741–2814. Springer, New York (2013)

Chapter   Google Scholar  

Buss, F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58 , 572–596 (1999)

Dontchev, A.L., Rockafellar, R.T.: Implicit functions and solution mappings—a view from variational analysis. Springer, Berlin (2009)

Drezner, Z.: The quadratic assignment problem, location science, pp. 345–363. Springer, New York (2015)

Google Scholar  

Drezner, Z., Hahn, P., Taillard, É.D.: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Oper. Res. 139 , 65–94 (2005)

MathSciNet   MATH   Google Scholar  

Coste, M.: An Introduction to o-minimal geometry. RAAG notes. Institut de Recherche Mathématiques de Rennes, Rennes (1999)

Fu, T., Ge, D., Ye, Y.: On doubly positive semidefinite programming relaxations. J. Comput. Math. 36 , 391–403 (2018)

Gao, Y.: Structured low rank matrix optimization problems: a penalized approach. PhD thesis, National University of Singapore (2010)

Gao, Y., Sun, D.F.: A majorized penalty approach for calibrating rank constrained correlation matrix problems. http://www.mypolyuweb.hk/~dfsun/MajorPen_May5.pdf (Preprint) (2010)

Hahn, P., Anjos, M.: QAPLIB—a quadratic assignment problem library. http://www.seas.upenn.edu/qaplib

Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge Univeristy Press, New York (1985)

Ioffe, A.D.: An invitation to tame optimization. SIAM J. Optim. 19 , 1894–1917 (2009)

Kim, S., Kojima, M., Toh, K.C.: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156 , 161–187 (2016)

Koopmans, T.C., Beckmann, M.J.: Assignment problems and the location of economics activities. Econometrica 25 , 53–76 (1957)

Li, Q., Qi, H.-D.: A sequential semismooth newton method for the nearest low-rank correlation matrix problem. SIAM J. Optim. 21 , 1641–1666 (2011)

Lin, C.-J., Saigal, R.: On solving large-scale semidefinite programming problems a case study of quadratic assignment problem. Technical report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI (1997)

Liu, T., Pong, T.K., Takeda, A.: A refined convergence analysis of with applications to simultaneous sparse recovery and outlier detection. Comput. Optim. Appl. 73 , 69–100 (2019)

Mishra, B.: Algorithmic Algebra. Springer, New York (1993)

Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turan. Can. J. Math. 17 , 533–540 (1965)

Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39 , 117–129 (1987)

Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18 , 223–241 (2007)

Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discr. Optim. 6 , 231–241 (2009)

Ramana, M., Tunçel, L., Wolkowicz, H.: Strong duality for semidefinite programming. SIAM J. Optim. 7 , 641–662 (1997)

Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109 , 505–524 (2007)

Rockafellar, R.T.: Convex Analyis. Princeton University Press, Princeton (1970)

Book   Google Scholar  

Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM 23 , 555–565 (1976)

Sun, D.F., Toh, K.C., Yuan, Y.C., Zhao, X.Y.: SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0), Optimization Methods and Software (in print) (2019)

Pham, D.T., Le Thi, H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. ACTA Math. Vietnam. 22 , 289–355 (1997)

Pham, D.T., Le Thi, A.: ADC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8 , 476–505 (1998)

Todd, M.J.: Semidefinite optimization. Acta Num. 10 , 515–560 (2001)

Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38 , 49–75 (1996)

Wen, Z.W., Goldfarb, D., Yin, W.T.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2 , 203–230 (2010)

Weyl, H.: Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung. Math. Ann. 71 , 441–479 (1912)

Yang, L.Q., Sun, D.F., Toh, K.C.: SDPNAL+: a majorized semismooth Newton-CG augmented lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7 , 331–366 (2015)

Yoshise, A., Matsukawa, Y.: On optimization over the doubly nonnegative cone. In: Proceedings of 2010 IEEE Multi-conference on Systems and Control, pp. 13–19 (2010)

Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2 , 71–109 (1998)

Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-CG augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20 , 1737–1765 (2010)

Download references

Acknowledgements

We would like to thank Dr. Xudong Li and Dr. Ying Cui for many helpful discussions on this work. Also, we would like to thank the two anonymous referees and the associate editor for their valuable comments and constructive suggestions which have helped to improve the quality of this paper.

X. Zhao: The research of this author was supported by the National Natural Science Foundation of China under projects No. 11871002 and the General Program of Science and Technology of Beijing Municipal Education Commission No. KM201810005004. C. Ding: The research of this author was supported by the National Natural Science Foundation of China under projects No. 11671387, No. 11531014 and No. 11688101 and the Beijing Natural Science Foundation (Z190002).

Author information

Authors and affiliations.

College of Applied Sciences, Beijing University of Technology, Beijing, People’s Republic of China

Zhuoxuan Jiang & Xinyuan Zhao

Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, People’s Republic of China

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Chao Ding .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Jiang, Z., Zhao, X. & Ding, C. A proximal DC approach for quadratic assignment problem. Comput Optim Appl 78 , 825–851 (2021). https://doi.org/10.1007/s10589-020-00252-5

Download citation

Received : 13 August 2019

Accepted : 02 December 2020

Published : 02 January 2021

Issue Date : April 2021

DOI : https://doi.org/10.1007/s10589-020-00252-5

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

  • Quadratic assignment problem
  • Doubly nonnegative programming
  • Augmented Lagrangian method
  • Rank constraint

Mathematics Subject Classification

  • Find a journal
  • Publish with us
  • Track your research

IMAGES

  1. PPT

    quadratic assignment problem applications

  2. PPT

    quadratic assignment problem applications

  3. PPT

    quadratic assignment problem applications

  4. 68 Solve Applications Involving Quadratic Functions (3.1)

    quadratic assignment problem applications

  5. 10 Real Life Applications Of Quadratic Equations

    quadratic assignment problem applications

  6. PPT

    quadratic assignment problem applications

VIDEO

  1. My favorite quadratic solving method

  2. Important Question on Quadratic Equations 😲 Can you solve this ⚡ #ytshorts #maths #practice

  3. Quadratic modelling

  4. Difficult question in Quadratic equations

  5. Solve The Quadratic Problem

  6. Quadratic Formula Assignment Instructions

COMMENTS

  1. Quadratic assignment problem

    Applications In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected electronic components onto a printed circuit board or on a microchip, which is part of the place and route stage of computer aided design in the electronics industry. See also

  2. Quadratic assignment problem

    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.

  3. A comprehensive review of quadratic assignment problem: variants

    The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields.

  4. Quadratic Assignment Problem (QAP)

    The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them. The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.

  5. PDF The Quadratic Assignment Problem

    The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in ... Let us conclude this section with a brief review of some of the many applications of the QAP. In addition to facility layout problems, the QAP appears in applications such as backboard wiring, computer manufacturing, scheduling, process communications, turbine ...

  6. Algebra

    Here is a set of assignement problems (for use by instructors) to accompany the Applications of Quadratic Equations section of the Solving Equations and Inequalities chapter of the notes for Paul Dawkins Algebra course at Lamar University.

  7. PDF A comprehensive review of quadratic assignment problem: variants

    The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems ... A comprehensive review of quadratic assignment problem: variants, hybrids and applications 1 3 These formulation has been applied in several researches such as Bazaraa and Elshafei (1979), Drezner (1995), Hahn and Grant ...

  8. Quadratic assignment problem variants: A survey and an effective

    Abstract In the Quadratic Assignment Problem (QAP), facilities are assigned to sites in order to minimize interactions between pairs of facilities. Although easy to define, it is among the hardest problems in combinatorial optimization, due to its non-linear nature.

  9. Quadratic Assignment Problems

    1 Introduction The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of indivisible economical activities [ 146 ].

  10. The Quadratic Assignment Problem: A Survey and Recent Developments

    This paper surveys some of the most important techniques, applications, and methods regarding the quadratic assignment problem and focuses on recent developments. Quadratic Assignment Problems model many applications in diverse areas such as operations research, parallel and distributed computing , and combinatorial data analysis. In this paper we survey some of the most important techniques ...

  11. A survey for the quadratic assignment problem

    The international literature identifies the quadratic assignment problem (QAP) as the problem of finding a minimum cost allocation of facilities into locations, taking the costs as the sum of all possible distance-flow products.

  12. 7. Quadratic Assignment Problems: Formulations and Bounds

    7.1 Introduction Quadratic assignment problems (QAPs) belong to the most difficult combinatorial optimization problems. Because of their many real-world applications, many authors have investigated this problem class. For a monograph on QAPs, see the book by Çela [180]. A volume with selected papers on this topic was edited by Pardalos and Wolkowicz [561]. Comprehensive surveys have been ...

  13. Quadratic Assignment Problem: A survey and Applications

    2017 TLDR A Modified Cuckoo Search (MCS) algorithm is presented to solve the Quadratic Assignment Problem (QAP), which is a NP-hard problem and is one of the most interesting and challenging combinatorial optimization problems in the research community. 3 PDF 1 Excerpt

  14. The Quadratic Assignment Problem: A Brief Review

    The quadratic assignment problem, its applications, and various exact and inexact procedures for its solution are briefly reviewed. Certain special cases of the one-dimensional module placement problem, itself a special case of the quadratic assignment problem, are surveyed. Keywords Assignment Problem Permutation Matrix Placement Problem

  15. The Quadratic Assignment Problem: An Analysis of Applications and

    Abstract A wide variety of practical problems in design, planning, and management can be formulated as quadratic assignment problems, and this paper discusses this class of problem.

  16. A Survey of the Quadratic Assignment Problem, with Applications

    Corpus ID: 941073 A Survey of the Quadratic Assignment Problem, with Applications C. Commander Published 2003 Mathematics TLDR This thesis will be a survey of the Quadratic Assignment Problem, addressing issues pertaining to the computational complexity of the QAP, lower bounds and exact algorithms. plaza.ufl.edu Save to Library Create Alert Cite

  17. The Quadratic Assignment Problem

    Abstract. This paper presents a formulation of the quadratic assignment problem, of which the Koopmans-Beckmann formulation is a special case. Various applications for the formulation are discussed. The equivalence of the problem to a linear assignment problem with certain additional constraints is demonstrated. A method for calculating a lower ...

  18. The Quadratic Assignment Problem

    The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of a set of indivisible economical activities [113]. ... R. E. Burkard and T. Bönniger, A heuristic for quadratic boolean programs with applications to quadratic assignment problems, European Journal of Operational ...

  19. Algebra

    Section 2.5 : Quadratic Equations - Part I. For problems 1 - 15 solve the quadratic equation by factoring. For problems 16 - 18 use factoring to solve the equation. For problems 19 - 22 use factoring to solve the equation. For problems 23 - 31 use the Square Root Property to solve the equation.

  20. A new tool for automated transformation of Quadratic Assignment Problem

    The Quadratic Assignment Problem (QAP) is one of the hardest optimisation problems, and it is widely used in real life applications. The problem consists of two matrices namely flow and distance. Let f i j be the flow between facilities i and j; and let d i j be the distance between sites i and j. In its simplest form, the optimal assignment of ...

  21. A proximal DC approach for quadratic assignment problem

    The quadratic assignment problem (QAP) is a classical mathematical model for location theory, which is used to model the location problem of allocating n facilities to n locations while minimizing the quadratic objective coming from the distance between the locations and the flow between the facilities.

  22. A comprehensive review of quadratic assignment problem: variants

    The quadratic assignment problem (QAP) has considered one of the most significant combinatorial optimization problems due to its variant and significant applications in real life such as scheduling, production, computer manufacture, chemistry, facility location, communication, and other fields.

  23. Quadratic Assignment Problems

    This chapter discusses the quadratic assignment problems (QAPs). The benefit or cost resulting from an economic activity at some location is dependent on the locations of other facilities. ... (A Heuristic for Quadratic Boolean Programs With Applications to Quadratic Assignment Problems)), European Journal of Operational Research 13, 374 - 386 ...