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 np complete proof

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 np complete proof

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

Quadratic Assignment Problem

  • Reference work entry
  • pp 3119–3149
  • Cite this reference work entry

quadratic assignment problem np complete proof

  • Leonidas Pitsoulis 3 &
  • Panos M. Pardalos 4  

854 Accesses

6 Citations

Article Outline

Formulations

Linearizations

  Lawler's Linearization

  Kaufman–Broeckx Linearization

  Frieze–Yadegar Linearization

  Adams–Johnson Linearization

Complexity Issues

  Computational Complexity

  PLS-Complexity

  Asymptotic Behavior

  Polynomially Solvable Cases

Lower Bounds

  Gilmore–Lawler Type Lower Bounds

  Variance Reduction Lower Bounds

  Eigenvalue Based Lower Bounds

  Bounds Based on Semidefinite Relaxations

Exact Solution Methods

  Branch and Bound

  Traditional Cutting Plane Methods

  Polyhedral Cutting Planes

  Construction Methods

  Limited Enumeration Methods

  Improvement Methods

  Tabu Search

  Simulated Annealing

  Genetic Algorithms

  Greedy Randomized Adaptive Search Procedure

  Ant Systems

Related Problems

  Biquadratic Assignment Problem

  Multidimensional Assignment Problems

  Bottleneck QAP

  Other Problems Which Can Be Formulated As QAPs

QAP Problem Generators

Surveys and Books

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

Access this chapter

  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Aarts E, Lenstra JK (eds) (1997) Local search in combinatorial optimization. Wiley, New York

MATH   Google Scholar  

Adams WP, Johnson TA (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic Assignment and Related Problems. DIMACS. Amer. Math. Soc., Providence, pp 43–75

Google Scholar  

Adams WP, Sherali HD (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Managem Sci 32(10):1274–1290

MATH   MathSciNet   Google Scholar  

Adams WP, Sherali HD (1990) Linearization strategies for a class of zero-one mixed integer programming problems. Oper Res 38(2):217–226

Ahuja RK, Orlin JB, Tivari A (1995) A greedy genetic algorithm for the quadratic assignment problem. Techn Report 3826-95, Sloan School Management

Arora S, Frieze A, Kaplan H (1996) A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In: Proc. 37-th Annual IEEE Symp. Foundations of Computer Sci. (FOCS). IEEE, New York, pp 21–30

Balas E, Mazzola JB (1980) Quadratic 0-1 programming by a new linearization. In: Proc TIMS/ORSA, May 1980

Balas E, Mazzola JB (1984) Nonlinear programming: I. Linearization techniques. Math Program 30:1–21

Article   MATH   MathSciNet   Google Scholar  

Balas E, Mazzola JB (1984) Nonlinear programming: II. Dominance relations and algorithms. Math Program 30:22–45

Balas E, Qi L (1993) Linear-time separation algorithms for the three-index assignment polytope. Discrete Appl Math (1993):1–12

Balas E, Saltzman MJ (1989) Facets of the three-index assignment polytope. Discrete Appl Math (1989):201–229

Battiti R, Tecchiolli G (1994) The reactive tabu search. ORSA J Comput (1994):126–140

Bazaraa MS, Sherali HD (1980) Bender's partitioning scheme applied to a new formulation of the quadratic assignment problem. Naval Res Logist Quart 27:29–41

Bazaraa MS, Sherali HD (1982) On the use of exact and heuristic cutting plane methods for the quadratic assignment problem. J Oper Res Soc 33:991–1003

Birkoff G (1946) Tres observaciones sobre el algebra lineal. Univ Nac Tucuman Rev (A):147–151

Bollobás B (1978) Extremal graph theory. Acad. Press, New York

Buffa ES, Armour GC, Vollmann TE (1962) Allocating facilities with CRAFT. Harvard Business Rev 42:136–158

Burkard RE (1973) Die Störungsmethode zur Lösung quadratischer Zuordnungsprobleme. Oper Res Verfahren 16:84–108

Burkard RE (1974) Quadratische Bottleneckprobleme. Oper Res Verfahren 18:26–41

MathSciNet   Google Scholar  

Burkard RE (1991) Locations with spatial interactions: the quadratic assignment problem. In: Mirchandani PB, Francis RL (eds) Discrete Location Theory. Wiley, New York

Burkard RE, Bönniger T (1983) A heuristic for quadratic Boolean programs with applications to quadratic assignment problems. Europ J Oper Res 13:374–386

Article   MATH   Google Scholar  

Burkard RE, Çela E (1995) Heuristics for biquadratic assignment problems and their computational comparison. Europ J Oper Res 83:283–300

Burkard RE, Çela E, Demidenko VM, Metelski NN, Woeginger GJ (1997) Perspectives of easy and hard cases of the quadratic assignment problems. Techn Report SFB 104, Techn Univ Graz

Burkard RE, Çela E, Klinz B (1994) On the biquadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS. Amer. Math. Soc., Providence, pp 117–146

Burkard RE, Çela E, Pardalos PM, Pitsoulis LS (1998) The quadratic assignment problem. In: Du D-Z and Pardalos PM (eds) Handbook Combinatorial Optim., vol 3. Kluwer, Dordrecht, pp 241–337

Burkard RE, Çela E, Rote G, Woeginger GJ (1995) The quadratic assignment problem with an Anti-Monge and a Toeplitz matrix: Easy and hard cases. Techn Report SFB 34, Techn Univ Graz

Burkard RE, Fincke U (1982) On random quadratic bottleneck assignment problems. Math Program 23:227–232

Burkard RE, Fincke U (1983) The asymptotic probabilistic behaviour of quadratic sum assignment problems. Z Oper Res 27:73–81

Burkard RE, Fincke U (1985) Probabilistic asymptotic properties of some combinatorial optimization problems. Discrete Appl Math 12:21–29

Burkard RE, Hahn W, Zimmermann U (1977) An algebraic approach to assignment problems. Math Program 12:318–327

Burkard RE, Karisch S, Rendl F (1997) QAPLIB – Aquadratic assignment problem library. J Global Optim 10:391–403

Burkard RE, Klinz B, Rudolf R (1996) Perspectives of Monge properties in optimization. Discrete Appl Math 70:95–161

Burkard RE, Rendl F (1984) A thermodynamically motivated simulation procedure for combinatorial optimization problems. Europ J Oper Res 17:169–174

Burkard RE, Zimmermann U (1982) Combinatorial optimization in linearly ordered semimodules: A survey. Modern Applied Mathematics. North-Holland, Amsterdam, pp 392–436

Çela E (1998) The quadratic assignment problem: Theory and algorithms. Kluwer, Dordrecht

Chakrapani J, Skorin-Kapov J (1993) Massively parallel tabu search for the quadratic assignment problem. Ann Oper Res 41:327–342

Christofides N (1976) Worst case analysis of a new heuristic for the traveling salesman problem. Grad School Industr Admin Carnegie-Mellon Univ 338

Colorni A, Dorigo M, Maniezzo V (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst, Man Cybern Part B 26:29–41

Article   Google Scholar  

Colorni A, Maniezzo V (1998) The ant system applied to the quadratic assignment problem. IEEE Trans Knowledge and Data Enginto

Connolly DT (1990) An improved annealing scheme for the QAP. Europ J Oper Res 46:93–100

Conrad K (1971) Das quadratische Zuweisungsproblem und zwei seiner Spezialfalle. Mohr-Siebeck, Tübingen

Cyganski D, Vaz RF, Virball VG (1994) Quadratic assignment problems with the Palubeckis' algorithm are degenerate. IEEE Trans Circuits and Systems I 41:481–484

Article   MathSciNet   Google Scholar  

Davis L (1987) Genetic algorithms and simulated annealing. Pitman, Boston

Deneko VG, Woeginger GJ (1996) A solvable case of the quadratic assignment problem. Techn Report SFB 88,Inst Math, Techn Univ Graz

Dorigo M (1992) Optimization, learning, and natural algorithms. PhD Thesis, Dip. Elettronica e Informazione Politecn. Milano. (In Italian)

Dyer ME, Frieze AM, McDiarmid CJH (1986) On linear programs with random costs. Math Program 35:3–16

Edwards CS (1980) A branch and bound algorithm for the Koopmans–Beckman quadratic assignment problem. Math Program Stud 13:35–52

Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Global Optim 6:109–133

Feo TA, Resende MGC, Smith SH (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 42:860–878

Finke G, Burkard RE, Rendl F (1984) Eigenvalue approach to quadratic assignment problems. In: 5th Symp. Oper. Res., 1984

Finke G, Burkard RE, Rendl F (1987) Quadratic assignment problems. Ann Discret Math 31:61–82

Fleurent C, Ferland J (1994) Genetic hybrids for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS. Amer. Math. Soc., Providence pp 43–75

Floudas CA, Pardalos PM (1990) A collection of test problems for constrained global optimization algorithms. Lecture Notes Computer Sci, vol 455. Springer, Berlin

Frenk JCB, van Houweninge M and, Rinnooy Kan AHG (1985) Asymptotic properties of assignment problems. Math Oper Res 10:100–116

Frieze AM (1974) A bilinear programming formulation of the 3-dimensional assignment problem. Math Program 7:376–379

Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl Math 5:89–98

Gambardella LM, Taillard ED, Dorigo M (1997) Ant colonies for the QAP. Techn Report IDSIA-4-97, Ist dalle Molle Di Studi sull'Intelligenza Artificiale Lugano

Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman, New York

Gavett JW, Plyter NV (1966) The optimal assignment of facilities to locations by branch and bound. Oper Res 14:210–232

Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J Appl Math 10:305–313

(1993) Tabu search. Ann Oper Res 41

Glover F (1989) Tabu search – Part I. ORSA J Comput 1:190–206

Glover F (1990) Tabu search – Part II. ORSA J Comput 2:4–32

Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading

Hadley SW (1989) Continuous optimization approaches for the quadratic assignment problem. PhD Thesis, Univ. Waterloo

Hadley SW, Rendl F, Wolkowicz H (1990) Bounds for the quadratic assignment problem using continuous optimization techniques. Integer Programming and Combinatorial Optimization. Univ. Waterloo Press, Waterloo, pp 237–248

Hadley SW, Rendl F, Wolkowicz H (1992) A new lower bound via projection for the quadratic assignment problem. Math Oper Res 17(3):727–739

Hadley SW, Rendl F, Wolkowicz H (1992) Nonsymmetric quadratic assignment problems and the Hoffman–Wielandt Inequality. Linear Alg & its Appl 58:109–124

Hardy GG, Littlewood JE, Polya G (1952) Inequalities. Cambridge Univ. Press, Cambridge

Heider CH (1972) A computationally simplified pair exchange algorithm for the quadratic assignment problem. Paper 101, Center Naval Anal, Arlington

Jansen B (1993) A note on lower bounds for the QAP. Techn Report (dec), Delft Univ Techn Math and Computer Sci

Johnson DS, Papadimitriou CH, Yannakakis M (1988) How easy is local search? J Comput Syst Sci 37:79–100

Johnson TA (1992) New linear programming-based solution procedures for the quadratic assignment problem. PhD Thesis, Clemson Univ.

Jünger M (1985) Polyhedral combinatorics and the acyclic subdigraph problem. Heldermann, Berlin

Kaibel V (1997) Polyhedral combinatorics of the quadratic assignment problem. PhD Thesis, Univ. Köln

Karisch SE (1995) Nonlinear approaches for quadratic assignment and graph partition problems. PhD Thesis, Techn. Univ. Graz

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

Karisch SE, Rendl F, Wolkowicz H (1994) Trust regions and the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS. Amer. Math. Soc., Providence, pp 199–220

Karp R (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Proc. Complexity of Computer Computations. Plenum, New York, pp 85–104

Kaufman L, Broeckx F (1978) An algorithm for the quadratic assignment problem using Benders' decomposition. Europ J Oper Res 2:204–211

Kernighan B, Lin S (1972) An efficient heuristic procedure for partitioning graphs. Bell Systems J 49:291–307

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680

Klincewicz JG (1992) Avoiding local optima in the p-hub location problem using tabu search and GRASP. Ann Oper Res 40:283–302

Klincewicz JG, Rajan A (1992) Using GRASPto solve the component grouping problem. Techn Report, AT&T Bell Lab

Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economic activities. Econometrica 25:53–76

Land AM (1963) A problem of assignment with interrelated costs. Oper Res Quart 14:185–198

Laporte G, Mercure H (1988) Balancing hydraulic turbine runners: A quadratic assignment problem. Europ J Oper Res 35:378–382

Lawler EL (1963) The quadratic assignment problem. Managem Sci 9:586–599

Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1985) The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, New York

Lengauer T (1990) Combinatorial algorithms for intergrated circuit layout. Wiley, New York

Leontief W (1966) Input–output economics. Oxford Univ. Press, Oxford

Li Y, Pardalos PM (1992) Generating quadratic assignment test problems with known optimal permutations. Comput Optim Appl 1(2):163–184

Li Y, Pardalos PM, Ramakrishnan KG, Resende MGC (1994) Lower bounds for the quadratic assignment problem. Ann Oper Res 50:387–410

Li Y, Pardalos PM, Resende MGC (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS 16. Amer. Math. Soc., Providence, pp 237–261

Mavridou T, Pardalos PM, Pitsoulis LS, Resende MGC (1998) A GRASPfor the biquadratic assignment problem. Europ J Oper Res 105(3):613–621

Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E (1953) Equations of state calculations by fast computing machines. J Chem Phys 21:1087–1092

Mirchandani PB, Obata T (1979) Locational decisions with interactions between facilities: the quadratic assignment problem a review. Working Paper May Ps-79-1, Rensselaer Polytechnic Inst, Troy, New York

Mirsky L (1956) The spread of a matrix. Mathematika 3:127–130

Mosevich J (1986) Balancing hydraulic turbine runners – a discrete combinatorial optimization problem. Europ J Oper Res 26:202–204

Muller-Merbach H (1970) Optimale Reihenlorgen. Springer, Berlin

Murphey RA, Pardalos PM, Pitsoulis L (1997) A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem. In: Pardalos PM, Du D-Z (eds) Network Design: Connectivity and Facility Location. DIMACS 40. Amer. Math. Soc., Providence, pp 277–302

Murphey RA, Pardalos PM, Pitsoulis L (1998) A parallel GRASP for the data association multidimensional assignment problem. Parallel Processing of Discrete Problems. In: IMA vol Math Appl, vol 106. Springer, Berlin, pp 159–180

Murthy KA, Pardalos PM, Li Y (1992) A local search algorithm for the quadratic assignment problem. Informatica 3(4):524–538

Murty KG (1968) An algorithm for ranking all the assignments in order of increasing cost. Oper Res 16:682–287

Nugent CE, Vollmann TE, Ruml J (1969) An experimental comparison of techniques for the assignment of facilities to locations. J Oper Res 16:150–173

Padberg MW, Rijal MP (1996) Location, scheduling, design and integer programming. Kluwer, Dordrecht

Palubetskis GS (1988) Generation of quadratic assignment test problems with known optimal solutions. Zh Vychisl Mat Mat Fiz 28(11):1740–1743. (In Russian.)

Papadimitriou CH, Wolfe D (1985) The complexity of facets resolved. In: Proc Foundations Computer Sci, pp 74–78

Pardalos PM, Pitsoulis LS, Resende MGC (1995) A parallel GRASP implementation for solving the quadratic assignment problem. In: Ferreira A and Rolim JDP (eds) Parallel Algorithms for Irregular Problems: State of the Art. Kluwer, Dordrecht, pp 115–133

Pardalos PM, Pitsoulis LS, Resende MGC (1997) Algorithm 769: FORTRAN subroutines for approximate solution of sparse quadratic assignment problems. ACM Trans Math Softw 23:196–208

Pardalos PM, Ramakrishnan KG, Resende MGC, Li Y (1997) Implementation of a variable reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem. SIAM J Optim 7(1):280–294

Pardalos PM, Rendl F, Wolkowicz H (1994) The quadratic assignment problem: A survey and recent developments. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS vol 16. Amer. Math. Soc., Providence, pp 1–42

Pardalos PM, Wolkowicz H (1994) Quadratic assignment and related problems. DIMACS, vol 16. Amer. Math. Soc., Providence

Pardalos PM, Xue Jue (1994) The maximum clique problem. J Global Optim 4:301–328

Pierskalla WP (1967) The tri-substitution method for the three-multidimensional assignment problem. CORS J 5:71–81

Pierskalla WP (1968) The multidimensional assignment problem. Oper Res 16:422–431

Pitsoulis LS (1998) Algorithms for nonlinear assignment problems. PhD Thesis, Dept. Industr. Systems Engin., Univ. Florida

Poore AB, Rijavec N (1994) Partitioning multiple data sets: multidimensional assignments and Lagrangian relaxation. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems. DIMACS vol 16. Amer. Math. Soc., Providence, pp 317–342

Pusztaszeri J, Rensing PE, Liebling TM (1995) Tracking elementary particles near their primary vertex: A combinatorial approach. J Global Optim 16:422–431

Qi L, Balas E, Gwan G (1994) A new facet class and a polyhedral method for the three-index assignment problem. In: Du D-Z (ed) Advances in Optimization. Kluwer, Dordrecht, pp 256–274

Queyranne M (1986) Performance ratio of heuristics for triangle inequality quadratic assignment problems. Oper Res Lett 4:231–234

Reinelt G (1985) The linear ordering problem: Algorithms and applications Res and Exposition in Math, vol 8. Heldermann, Berlin

Rendl F (1985) Ranking scalar products to improve bounds for the quadratic assignment problem. Europ J Oper Res 20:363–372

Rendl F, Wolkowicz H (1992) Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem. Math Program 53:63–78

Resende MGC, Pitsoulis LS, Pardalos PM (1997) Approximate solution of weighted MAX-SAT problems using GRASP. In: Pardalos PM Resende MGC, Du DZ (eds) The Satisfiability Problem. DIMACS vol 35. Amer. Math. Soc., Providence, pp 393–405

Rhee WT (1989) A note on asymptotic properties of the quadratic assigment problem. Oper Res Lett 4:197–200

Rhee WT (1991) Stochastic analysis of the quadratic assignment problem. Math Oper Res 2:223–239

Roucairol C (1979) A reduction method for quadratic assignment problems. Oper Res Verfahren 32:183–187

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

Schäffer AA, Yannakakis M (1991) Simple local search problems that are hard to solve. SIAM J Comput 20:56–87

Skorin-Kapov J (1990) Tabu search applied to the quadratic assignment problem. ORSA J Comput 2(1):33–45

Szpankowski W (1995) Combinatorial optimization problems for which almost every algorithm is asymptotically optimal! Optim 33:359–367

Taillard E (1991) Robust tabu search for the quadratic assignment problem. Parallel Comput 17:443–455

Tate DM, Smith AE (1995) A genetic approach to the quadratic assignment problem. Comput Oper Res 22:73–83

Ĉerný V (1985) Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. J Optim Th Appl 45:41–51

Wilhelm MR, Ward TL (1987) Solving quadratic assignment problems by simulated annealing. IEEE Trans 19(1):107–119

Zhao Q (1996) Semidefinite programming for assignment and partitioning problems. PhD Thesis, Univ. Waterloo

Download references

Author information

Authors and affiliations.

Princeton University, Princeton, USA

Leonidas Pitsoulis

Center for Applied Optim. Department Industrial and Systems Engineering, University Florida, Gainesville, USA

Panos M. Pardalos

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

Christodoulos A. Floudas

Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry.

Pitsoulis, L., Pardalos, P.M. (2008). Quadratic Assignment Problem . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_534

Download citation

DOI : https://doi.org/10.1007/978-0-387-74759-0_534

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-74758-3

Online ISBN : 978-0-387-74759-0

eBook Packages : Mathematics and Statistics Reference Module Computer Science and Engineering

Share this entry

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

  • Publish with us

Policies and ethics

  • Find a journal
  • Track your research
  • Analysis of Algorithms
  • Backtracking
  • Dynamic Programming
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Pattern Searching
  • Bitwise Algorithms
  • Branch & Bound
  • Randomized Algorithms

Quadratic Assignment Problem (QAP)

  • Channel Assignment Problem
  • Assignment Operators In C++
  • Solidity - Assignment Operators
  • Job Assignment Problem using Branch And Bound
  • Range Minimum Query with Range Assignment
  • Transportation Problem | Set 1 (Introduction)
  • Transportation Problem | Set 2 (NorthWest Corner Method)
  • Transportation Problem | Set 3 (Least Cost Cell Method)
  • Transportation Problem | Set 4 (Vogel's Approximation Method)
  • Assignment Operators in C
  • QA - Placement Quizzes | Profit and Loss | Question 7
  • QA - Placement Quizzes | Profit and Loss | Question 4
  • QA - Placement Quizzes | Profit and Loss | Question 12
  • QA - Placement Quizzes | Profit and Loss | Question 10
  • QA - Placement Quizzes | Profit and Loss | Question 8
  • QA - Placement Quizzes | Age | Question 4
  • QA - Placement Quizzes | Profit and Loss | Question 9
  • QA - Placement Quizzes | Profit and Loss | Question 11
  • IBM Placement Paper | Quantitative Analysis Set - 5
  • Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...
  • Top 50 Array Coding Problems for Interviews
  • Introduction to Recursion - Data Structure and Algorithm Tutorials
  • Difference between BFS and DFS
  • Must Do Coding Questions for Product Based Companies
  • A* Search Algorithm
  • Top 10 Algorithms in Interview Questions
  • Sliding Window Technique
  • How to write a Pseudo Code?
  • Asymptotic Notation and Analysis (Based on input size) in Complexity Analysis of Algorithms
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...

Similar reads.

advertisewithusBannerImg

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

COMMENTS

  1. Quadratic assignment problem

    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.

  2. PDF A Survey of the Quadratic Assignment Problem, with Applications

    The quadratic assignment problem (QAP) was originally introduced in 1957 by Tjalling C. Koopmans and Martin Beckman [26] who were trying to ... of computationally hard problems known as NP-complete. The proof that the QAP is indeed NP-complete was first shown by Sahni and Gonzalez [39] in 1976. Belonging to this class of problems suggests that

  3. PDF 6.045 Pset 5: NP-Completeness and More

    Let EXACT 4SAT be the following problem: • Given a Boolean formula φ, consisting of an AND of clauses involving exactly 4 distinct literals each (such as (x2∨ x3∨ x5 ∨ x6)), decide whether φ is satisfiable. Show that EXACT 4SAT is NP-complete. You can use the fact, which we proved in class, that 3SAT is NP-complete. 2.

  4. PDF Project

    The Quadratic Assignment Problem (QAP) is a fundamental combinato- ... 2.2 NP-Completeness Proof ... To prove that the problem is NP-complete, I'll show that the TSP re-duces to QAP. Here is a decision version of TSP: For a given set V with a distance metric d(a,b),a,b ∈ V, and a number ...

  5. Quadratic assignment problem

    The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Koopmans and Beckmann.. The problem models the following real-life problem: There are a set of n facilities and a set of n locations.

  6. 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. QAP is NP-hard problem that is impossible to be solved in polynomial time when the problem size ...

  7. PDF Lecture 8: NP-complete problems

    lecture 8: np-complete problems 4 Hamiltonian Path Given a directed graph G, a Hamiltonian path is a path that visits every vertex of the graph exactly once. We define the function HPATH(G) = 1 if G has a Hamiltonian path 0 otherwise. Theorem 3. HPATH is NP-complete. Proof Given a path in the graph, one can check in polynomial time

  8. Quadratic Assignment Problems

    The quadratic assignment problem is strongly NP-hard. ... The proof of equivalence of the QAP to the mixed integer linear program can be found in ... there exist complete problems in the class of PLS problems. The PLS-complete problems are—in the usual sense of complexity—the most difficult among the PLS problems. In connection to QAPs, the ...

  9. Quadratic Assignment Problem

    The proof of equivalence of the QAP to the above linear integer program can be found in ... The quadratic assignment problem is strongly NP-hard. ... problem for which local optimality can be checked in polynomial time. In analogy with decision problems, there exist complete problems in the class of PLS problems. The PLS-complete problems, are ...

  10. PDF Equality of Complexity Classes P and NP: A Linear Programming

    The Quadratic Assignment Problem (QAP) is the problem of making exclusive assignments ... Problem QAP was shown to be NP-Hard as far back as the 1970's (Sahni and Gonzales [1976]). Moreover, it has been known for some time that the Traveling Salesman Problem (see Lawler et al. [1985]) and other NP-Complete combinatorial optimization problems ...

  11. A survey for the quadratic assignment problem

    The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph ...

  12. PDF On the Equality of Complexity Classes P NP: Formulation of the

    The Quadratic Assignment Problem (QAP) is the problem of ... time that the Traveling Salesman Problem (see [3]) and other NP-complete combinatorial optimization problems (see [4], [5], or [6]) can be modeled as special cases of the problem. ... a proof of the

  13. PDF Lecture 3: Examples of NP-Complete Problems

    We show that Quadeq is NP-complete Task :- Check if they are solvable i.e. if 9a 0/1 assignment of variables that satis es all the equations. Claim :- Quadeq is NP-Complete. Proof:- Given decision problem belongs to NP-class since for a given value of x 1;x 2;:::;x n veri er can verify if each equations are satis ed in polynomial time.

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

  15. List of NP-complete problems

    Quadratic assignment problem: ... (3SAT), since it is used in the proof of many other NP-completeness results.: ... This book is a classic, developing the theory, then cataloguing many NP-Complete problems. Cook, S.A. (1971). "The complexity of theorem proving procedures".

  16. PDF arXiv:1409.0375v3 [cs.CC] 23 Nov 2014

    Nowadays a topical question is wether NP-complete problems are intractable. A proof of the possibility to solve an NP-complete problem with a polynomial ... P versus NP problem. Quadratic assignment problem. 1. 2 ANATOLY PANYUKOV 3. Locationof vertices of cycleC ongraph G Let C be a simple cycle, V (C) = {c0,c1,...,cn−1} be a set of vertices and

  17. PDF Lecture 7: NP-Complete Problems

    Lecture 7: NP-Complete Problems. Theorem 2. ISET is NP-complete. Proof ISET is in NP, since the independent set of largest size is itself a witness which can be verified in polynomial time. Thus it only remains to show that ISET is NP-hard. To do this, we show how to reduce 3SAT to ISET in polynomial time. Given a 3SAT instance with m clauses ...

  18. PDF Lecture 24: Classical NP-hard Problems

    Lecture 24: Classical NP-hard Problems Lecturer: Rong Ge Scribe: Shweta Patwa Outline: Hamiltonian Path to TSP 3-SAT to quadratic program Tripartite Matching to SUBSET SUM 1 General recipe for doing reductions In order to prove that B is NP-hard, given that we know A is NP-hard. Reduce A to B (and NOT in the other direction). Steps: 1.

  19. PDF List of NP-complete problems

    NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem. Domatic partition, a.k.a. domatic number[4] Graph coloring, a.k.a. chromatic number[1][5] Partition into cliques.

  20. 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. To model such location problems, QAP is introduced. The objective assigns the plants to the possible sites such that the total cost of building and operating ...

  21. Equality of Complexity Classes P and NP: A Linear Programming

    The Quadratic Assignment Problem (QAP) is the problem of making exclusive assignments of n indivisible entities to n other indivisible entities in such a way that a total quadratic interaction cost is minimized. The problem can be interpreted from a wide variety of perspectives. The perspective we adopt in this paper is that of the generic ...

  22. NP-complete decision problems for quadratic polynomials

    Because of the relative difficulty of the reduction of the satisfiability problem used in the proof, and the distinctly number-theoretic character of the problems shown to be NP-complete, we hope that the NP-completeness of these problems will play a role in showing the NP-completeness of further problems of a numerical nature, much as the ...

  23. [PDF] Equality of complexity classes P and NP: Linear programming

    A first linear programming formulation of the Quadratic Assignment Problem (QAP) is presented, a network flow-based model with 0(n9) variables and 0(n7) constraints, where n is the number of assignments, and represents a proof of the equality of the computational complexity classes P and NP. Expand

  24. Quadratic programming is in NP

    This concludes the proof that quadratic programming is in NP. Theorem 1. Problem QPL is NP-complete. Proof. Sahni's reduction or the reduction in the first section shows that any problem in NP can be polynotnially transformed to QPL. In the last two sections, we have argued that there is a polynomial-length certificate for yes-instances of QPL ...