\[\begin{array}{|c|c|c|}
\text{facility } i & \text{facility } j & \text{flow}(i,j) \\ \hline \hline
1 & 2 & 3 \\
1 & 4 & 2 \\
2 & 4 & 1 \\
3 & 4 & 4
\end{array}\]
\(\begin{array}{|c|c|c|}
\text{location } i & \text{location } j & \text{distance}(i,j) \\ \hline
1 & 3 & 53 \\
2 & 1 & 22 \\
2 & 3 & 40 \\
3 & 4 & 55
\end{array}\)
Then, the assignment cost of the permutation can be computed as \(f(1,2) \cdot d(2,1) + f(1,4) \cdot d(2,3) + f(2,4) \cdot d(1,3) + f(3,4) \cdot d(3,4)\) = \(3 \cdot 22 + 2 \cdot 40 + 1 \cdot 53 + 4 \cdot 55\) = 419. Note that this permutation is not the optimal solution.
Here we present the Koopmans-Beckmann formulation of the QAP. Given a set of facilities and locations along with the flows between facilities and the distances between locations, the objective of the Quadratic Assignment Problem is to assign each facility to a location in such a way as to minimize the total cost.
Sets \(N = \{1, 2, \cdots, n\}\) \(S_n = \phi: N \rightarrow N\) is the set of all permutations
Parameters \(F = (f_{ij})\) is an \(n \times n\) matrix where \(f_{ij}\) is the required flow between facilities \(i\) and \(j\) \(D = (d_{ij})\) is an \(n \times n\) matrix where \(d_{ij}\) is the distance between locations \(i\) and \(j\)
Optimization Problem \(\text{min}_{\phi \in S_n} \sum_{i=1}^n \sum_{j=1}^n f_{ij} \cdot d_{\phi(i) \phi(j)}\)
The assignment of facilities to locations is represented by a permutation \(\phi\), where \(\phi(i)\) is the location to which facility \(i\) is assigned. Each individual product \(f_{ij} \cdot d_{\phi(i) \phi(j)}\) is the cost of assigning facility \(i\) to location \(\phi(i)\) and facility \(j\) to location \(\phi(j)\).
Follow the links below to test your skill at finding good solutions to QAPs of various sizes. Notice that as the problem size increases, it becomes much more difficult to find an optimal solution. As \(n\) increases beyond a small number, it becomes impossible to enumerate and evaluate all possible assignment vectors. Instead, advanced solution algorithms are required to solve larger instances.
Qap of size 5, qap of size 6, qap of size 7, qap of size 8, qap of size 9.
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
Encyclopedia of Optimization
Panos Pardalos
Panos M Pardalos
Abstract This paper aims at describing the state of the art on quadratic assignment problems (QAPs). It discusses the most important developments in all aspects of the QAP such as linearizations, QAP polyhedra, algorithms to solve the problem to optimality, heuristics, polynomially solvable special cases, and asymptotic behavior.
Güneş Erdoğan
The Quadratic Assignment Problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed for instances of size larger than 15 have been generally unsuccessful even though successful implementations have been reported on some test problems from the QAPLIB up to size 36. In this dissertation, we analyze the binary structure of the QAP and present new IP formulations. We focus on “flow-based” formulations, strengthen the formulations with valid inequalities, and report computational experience with a branch-and-cut algorithm. Next, we present new classes of instances of the QAP that can be completely or partially reduced to the Linear Assignment Problem and give procedures to check whether or not an instance is an element of one of these classes. We also identify classes of instances of the Koopmans-Beckmann form of the QAP that are solvable in polynomial time. Lastly, we present a strong lower bound based on Bender’s decomposition.
Cesar Beltran-Royo
Pesquisa Operacional
Paulo Boaventura Netto
We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.
Computers & Operations Research
Ricardo P M Ferreira
Ilyes Beltaef
Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
Paulo Gonçalves
Dennis Heffley
Franz Rendl
Vittorio Maniezzo
New ideas in optimization
Marco Dorigo
Álvaro M. Valdebenito B.
Journal of Combinatorial Optimization
Madalina Drugan
Ali Safari Mamaghani
Informs Journal on Computing
Dushyant Sharma
Mathematics of Operations Research
Discrete Applied Mathematics
catherine roucairol
IEEE Transactions on Knowledge and Data Engineering
Cut Latifah
European Journal of Operational Research
Bernard Mans
Teodor Crainic
Applied Mathematical Sciences
Hassan Mishmast Nehi
Panos M Pardalos , John Mitchell
Paulo Boaventura-Netto
Ajay Bidyarthy
Yugoslav Journal of …
Journal of Industrial Engineering International
Hossein Karimi
NURDIYANA JAMIL
Ajith Abraham
IEEE Transactions on Information Theory
David Malah
Tansel Dökeroğlu
Matteo Fischetti
Sunderesh Heragu
Selected topics on assignment problems, new heuristic rounding approaches to the quadratic assignment problem, quadratic assignment problem: a survey and applications, a survey of quadratic assignment problems, a survey of the quadratic assignment problem, equality of complexity classes p and np: linear programming formulation of the quadratic assignment problem, on the equality of complexity classes p and np: linear programming formulation of the quadratic assignment problem, a survey of the quadratic assignment problem, with applications.
Quadratic and multidimensional assignment problems, 218 references, a parallel branch and bound algorithm for the quadratic assignment problem, a parallel algorithm for the quadratic assignment problem, quadratic assignment problems, a new lower bound for the quadratic assignment problem, applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, special cases of the quadratic assignment problem, on the mapping problem, a heuristic for quadratic boolean programs with applications to quadratic assignment problems, an introduction to parallelism in combinatorial optimization, a graph theoretic analysis of bounds for the quadratic assignment problem, related papers.
Showing 1 through 3 of 0 Related Papers
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Please log in to your account
Bibliometrics & citations, view options.
Information systems
Data management systems
Database administration
Data dictionaries
Mathematics of computing
Mathematical analysis
Numerical analysis
Numerical differentiation
Theory of computation
Design and analysis of algorithms
Mathematical optimization
An algorithm for the generalized quadratic assignment problem.
This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations ...
Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two ...
Quadratic assignment problems (QAPs) and quadratic assignment matchings (QAMs) recently gained a lot of interest in computer graphics and vision, e.g. for shape and graph matching. Literature describes several convex relaxations to approximate solutions ...
Published in.
Linthicum, MD, United States
Contributors, other metrics, bibliometrics, article metrics.
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Share this publication link.
Copying failed.
Export citations.
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
4526 Accesses
80 Citations
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]. Consider the problem of allocating a set of facilities to a set of locations, with the cost being a function of the distance and flow between the facilities, plus costs associated with a facility being placed at a certain location. The objective is to assign each facility to a location such that the total cost is minimized. Specifically, we are given three n x n input matrices with real elements F = ( f ij ), D = ( d kl ) and B = ( b ik ), where f ij is the flow between the facility i and facility j , d kl is the distance between the location k and location l , and b ik is the cost of placing facility i at location k . The Koopmans-Beckmann version of the QAP can be formulated as follows: Let n be the number of facilities and locations and denote by N the set N = {1, 2,..., n}.
These authors have been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.
This is a preview of subscription content, log in via an institution to check access.
Subscribe and save.
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
A linear formulation with $$o(n^2)$$ variables for quadratic assignment problems with manhattan distance matrices.
E. H. L. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing , Wiley, Chichester, 1989.
MATH Google Scholar
E. Aarts and J. K. Lenstra, eds., Local Search in Combinatorial Optimization , Wiley, Chichester, 1997.
W. P. Adams and T. A. Johnson, Improved linear programming-based lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems , P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science 16 , 1994, 43–75, AMS, Providence, RI.
Google Scholar
W. P. Adams and H. D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science 32 , 1986, 1274–1290.
Article MATH MathSciNet Google Scholar
W. P. Adams and H. D. Sherali, Linearization strategies for a class of zero-one mixed integer programming problems, Operations Research 38 , 1990, 217–226.
R. K. Ahuja, J. B. Orlin, and A. Tivari, A greedy genetic algorithm for the quadratic assignment problem, Working paper 3826–95, Sloan School of Management, MIT, 1995.
S. Arora, A. Frieze, and H. Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37-th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 1996, 21–30.
A. A. Assad, and W. Xu, On lower bounds for a class of quadratic 0–1 programs, Operations Research Letters 4 , 1985, 175–180.
E. Balas and J. B. Mazzola, Quadratic 0–1 programming by a new linearization, presented at the Joint ORSA/TIMS National Meeting , 1980, Washington D.C.
E. Balas and J. B. Mazzola, Nonlinear programming: I . Linearization techniques, Mathematical Programming 30 , 1984, 1–21.
E. Balas and J. B. Mazzola, Nonlinear programming: II. Dominance relations and algorithms, Mathematical Programming 30 , 1984, 2245.
A. I. Barvinok, Computational complexity of orbits in representations of symmetric groups, Advances in Soviet Mathematics 9 , 1992, 161–182.
MathSciNet Google Scholar
R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA Journal on Computing 6 , 1994, 126–140.
M. S. Bazaraa and O. Kirca, Branch and bound based heuristics for solving the quadratic assignment problem, Naval Research Logistics Quarterly 30 , 1983, 287–304.
M. S. Bazaraa and H. D. Sherali, Benders’ partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics Quarterly 27 , 1980, 29–41.
M. S. Bazaraa and H. D. Sherali, On the use of exact and heuristic cutting plane methods for the quadratic assignment problem, Journal of Operations Research Society 33 , 1982, 991–1003.
MATH MathSciNet Google Scholar
G. Birkhoff, Tres observaciones sobre el algebra lineal, Univ. Nac. Tucumán Rev., Ser. A , 1946, 147–151
B. Bollobâs, Extremal Graph Theory , Academic Press, London, 1978.
A. Bruengger, J. Clausen, A. Marzetta, and M. Perregaard, Joining forces in solving large-scale quadratic assignment problems in parallel, in Proceedings of the 11-th IEEE International Parallel Processing Symposium (IPPS) , 1997, 418–427.
E. S. Buffa, G. C. Armour, and T. E. Vollmann, Allocating facilities with CRAFT, Harvard Business Review 42, 1962, 136–158.
R. E. Burkard, Die Störungsmethode zur Lösung quadratischer Zuordnungsprobleme, Operations Research Verfahren 16 , 1973, 84–108.
R. E. Burkard, Quadratische Bottleneckprobleme, Operations Research Verfahren 18, 1974, 26–41.
R. E. Burkard, Locations with spatial interactions: the quadratic assignment problem, in Discrete Location Theory, P. B. Mirchandani and R. L. Francis, eds., Wiley, 1991.
R. E. Burkard and T. Bönniger, A heuristic for quadratic boolean programs with applications to quadratic assignment problems, European Journal of Operational Research 13, 1983, 374–386.
Article MATH Google Scholar
R. E. Burkard and E. Çela, Heuristics for biquadratic assignment problems and their computational comparison, European Journal of Operational Research 83 , 1995, 283–300.
R. E. Burkard, E. Çela, V. M. Demidenko, N. N. Metelski, and G. J. Woeginger, Perspectives of Easy and Hard Cases of the Quadratic Assignment Problems, SFB Report 104, Institute of Mathematics, Technical University Graz, Austria, 1997.
R. E. Burkard, E. Çela, and B. Klinz, On the biquadratic assignment problem, in Quadratic Assignment and Related Problems , P. M. Pardalos and H. Wolkowicz, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science 16, 1994, 117–146, AMS, Providence, RI.
R. E. Burkard, E. Çela, G. Rote, and G. J. Woeginger, The quadratic assignment problem with an Anti-Monge and a Toeplitz matrix: Easy and hard cases, SFB Report 34, Institute of Mathematics, Technical University Graz, Austria, 1995. To appear in Mathematical Programming.
R. E. Burkard and U. Derigs, Assignment and matching problems: Solution methods with Fortran programs, Lecture Notes in Economics and Mathematical Systems 184, Springer-Verlag, Berlin, 1980.
R. E. Burkard and U. Fincke, On random quadratic bottleneck assignment problems, Mathematical Programming 23 , 1982, 227–232.
R. E. Burkard and U. Fincke, The asymptotic probabilistic behavior of the quadratic sum assignment problem, Zeitschrift für Operations Research 27, 1983, 73–81.
R. E. Burkard and U. Fincke, Probabilistic asymptotic properties of some combinatorial optimization problems, Discrete Applied Mathematics 12, 1985, 21–29.
R. E. Burkard, W. Hahn and U. Zimmermann, An algebraic approach to assignment problems, Mathematical Programming 12 , 1977, 318–327.
R. E. Burkard, S. E. Karisch, and F. Rendl, QAPLIB-a quadratic assignment prob- lem library, Journal of Global Optimization 10, 1997, 391–403. An on-line version is available via World Wide Web at the following URL: http://www.opt.math.tu-graz.ac.at/karisch/gaplib/
Article MathSciNet Google Scholar
R. E. Burkard, B. Klinz, and R. Rudolf, Perspectives of Monge properties in optimization, Discrete Applied Mathematics 70, 1996, 95–161.
R. E. Burkard and J. Offermann, Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme, Zeitschrift für Operations Research 21 , 1977, B121–B132, (in German).
Article Google Scholar
R. E. Burkard and F. Rendl, A thermodynamically motivated simulation procedure for combinatorial optimization problems, European Journal Operational Research 17 , 1984, 169–174.
R. E. Burkard and U. Zimmermann, Combinatorial optimization in linearly ordered semimodules: a survey, in Modern Applied Mathematics , B. Korte, ed., North Holland, Amsterdam, 1982, 392–436.
P. Carraresi and F. Malucelli, A new lower bound for the quadratic assignment problem, Operations Research 40 , 1992, Suppl. No. 1 , S22–S27.
P. Carraresi and F. Malucelli, A reformulation scheme and new lower bounds for the QAP, in Quadratic Assignment and Related Problems , P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 , 1994, 147–160, AMS, Providence, RI.
E. Çela, The Quadratic Assignment Problem: Theory and Algorithms , Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998.
V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications 45 , 1985, 41–51.
J. Chakrapani and J. Skorin-Kapov, Massively parallel tabu search for the quadratic assignment problem, Annals of Operations Research 41 , 1993, 327–342.
J. Chakrapani and J. Skorin-Kapov, A constructive method to improve lower bounds for the quadratic assignment problem, in Quadratic Assignment and Related Problems , P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 , 1994, 161–171, AMS, Providence, RI.
P. Chretienne, A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints, European Journal of Operational Research 43 , 1989, 225–230.
N. Christofides, Worst case analysis of a new heuristic for the traveling salesman problem, Technical Report 338, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
N. Christofides and E. Benavent, An exact algorithm for the quadratic assignment problem, Operations Research 37 , 1989, 760–768.
N. Christofides and M. Gerrard, A graph theoretic analysis of bounds for the quadratic assignment problem, in Studies on Graphs and Discrete Programming , P. Hansen, ed., North Holland, 1981, pp. 61–68.
Chapter Google Scholar
J. Clausen, S. E. Karisch, M. Perregaard, and F. Rendl, On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel, Computational Optimization and Applications 10 , 1998, 127–147.
J. Clausen and M. Perregaard, Solving large quadratic assignment problems in parallel, Computational Optimization and Applications 8 , 1997, 111–127.
A. Colorni, M. Dorigo, and V. Maniezzo, The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems , Man , and Cybernetics -Part B 26 , 1996, 29–41.
A. Colorni and V. Maniezzo, The ant system applied to the quadratic assignment problem, to appear in IEEE Transactions on Knowledge and Data Engineering , 1998.
D. T. Connolly, An improved annealing scheme for the QAP, European Journal of Operational Research 46 , 1990, 93–100.
K. Conrad, Das Quadratische Zuweisungsproblem and zwei seiner Spezialfälle , Mohr-Siebeck, Tübingen, 1971.
D. Cyganski, R. F. Vaz, and V. G. Virball, Quadratic assignment problems with the Palubeckis’ algorithm are degenerate, IEEE Transactions on Circuits and Systems-I 41 , 1994, 481–484.
L. Davis, Genetic Algorithms and Simulated Annealing , Pitman, London, 1987.
V. G. Deineko and G. J. Woeginger, A solvable case of the quadratic assignment problem, SFB Report 88, Institute of Mathematics, Technical University Graz, Austria, 1996.
J. W. Dickey and J. W. Hopkins, Campus building arrangement using TOPAZ, Transportation Research 6 , 1972, 59–68.
M. Dorigo, Optimization, Learning, and Natural algorithms , Ph.D. Thesis, Dipartimento die Elettronica e Informazione, Politecnico di Milano, Milano, Italy, 1992, (in Italian).
M. E. Dyer, A. M. Frieze, and C. J. H. McDiarmid, On linear programs with random costs, Mathematical Programming 35 , 1986, 3–16.
C. S. Edwards, The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem, Proceedings of the 77-th Combinatorial Programming Conference (CP77) , 1977, 55–86.
C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study 13 , 1980, 35–52.
A. N. Elshafei, Hospital layout as a quadratic assignment problem, Operations Research Quarterly 28 , 1977, 167–179.
T. Espersen, S. E. Karisch, E. Cela, and J. Clausen, QAPPACK - a JAVA package for solving quadratic assignment problems, working paper, Department of Mathematical Modelling, Technical University of Denmark, Denmark, and Institute of Mathematics, Technical University Graz, Austria.
T. A. Feo, M. G. C. Resende, and S. H. Smith, A greedy randomized adaptive search procedure for the maximum independent set, Technical report, AT&T Bell Laboratories, Murray Hill, NJ, 1989. To appear in Operations Research .
T. A. Feo and M. G. C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 , 1995, 109–133.
G. Finke, R. E. Burkard, and F. Rendl, Quadratic assignment problems, Annals of Discrete Mathematics 31 , 1987, 61–82.
C. Fleurent and J. Ferland, Genetic hybrids for the quadratic assignment problem, in Quadratic Assignment and Related Problems , P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 , 1994, 173–187, AMS, Providence, RI.
J. B. G. Frenk, M. van Houweninge, and A. H. G. Rinnooy Kan, Asymptotic properties of the quadratic assignment problem, Mathematics of Operations Research 10 , 1985, 100–116.
A. M. Frieze and J. Yadegar, On the quadratic assignment problem, Discrete Applied Mathematics 5 , 1983, 89–98.
A. M. Frieze, J. Yadegar, S. El-Horbaty, and D. Parkinson, Algorithms for assignment problems on an array processor, Parallel Computing 11 , 1989, 151–162.
L. M. Gambardella, E. D. Taillard, and M. Dorigo, Ant colonies for the QAP, Technical Report IDSIA-4–97, 1997, Istituto dalle Molle Di Studi sull’ Intelligenza Artificiale, Lugano, Switzerland.
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness , W. H. Freeman and Company, New York, 1979.
J. W. Gavett and N. V. Plyter, The optimal assignment of facilities to locations by branch and bound, Operations Research 14 , 1966, 210–232.
A. M. Geoffrion, Lagrangean relaxation and its uses in integer programming, Mathematical Programming Study 2 , 1974, 82–114.
A. M. Geoffrion and G. W. Graves, Scheduling parallel production lines with changeover costs: Practical applications of a quadratic assignment/LP approach. Operations Research 24 , 1976, 595–610.
P. C. Gilmore, Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM Journal on Applied Mathematics 10 , 1962, 305–313.
F. Glover, Improved linear integer programming formulations of nonlinear integer problems, Management Science 22 , 1975, 455–460.
F. Glover, Tabu search-Part I, ORSA Journal on Computing 1 , 1989, 190–206.
F. Glover, Tabu search-Part II, ORSA Journal on Computing 2 , 1989, 4–32.
F. Glover, M. Laguna, E. Taillard, and D. de Werra, eds., Tabu search, Annals of Operations Research 41 , 1993.
M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42 , 1995, 1115–1145.
D. E. Goldberg, Genetic Algorithms in Search , Optimization and Machine Learning , Addison-Wesley, Wokingham, England, 1989.
A. Graham, Kronecker Products and Matrix Calculus with Applications , Halsted Press, Toronto, 1981.
H. Greenberg, A quadratic assignment problem without column constraints, Naval Research Logistic Quarterly 16 , 1969, 417–422.
S. W. Hadley, Continuous Optimization Approaches for the Quadratic Assignment Problem , PhD thesis, University of Waterloo, Ontario, Canada, 1989.
S. W. Hadley, F. Rendl, and H. Wolkowicz, Bounds for the quadratic assignment problem using continuous optimization techniques, Proceedings of the 1-st Integer Programming and Combinatorial Optimization Conference (IPCO) , University of Waterloo Press, 1990, 237–248.
S. W. Hadley, F. Rendl, and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem, Mathematics of Operations Research 17 , 1992, 727–739.
S. W. Hadley, F. Rendl, and H. Wolkowicz, Nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality, Linear Algebra and its Applications 58 , 1992, 109–124.
P. Hahn and T. Grant, Lower bounds for the quadratic assignment problem based upon a dual formulation, to appear in Operations Research.
P. Hahn, T. Grant, and N. Hall, Solution of the quadratic assignment problem using the Hungarian method, to appear in European Journal of Operational Research .
G. G. Hardy, J. E. Littlewood, and G. Pblya, Inequalities , Cambridge University Press, London and New York, 1952.
D. R. Hefiiey, Assigning runners to a relay team, in Optimal Strategies in Sports , S. P. Ladany and R. E. Machol, eds., North-Holland, Amsterdam, 1977, 169–171.
C. H. Heider, A computationally simplified pair exchange algorithm for the quadratic assignment problem, Paper No. 101, Center for Naval Analysis, Arlington, Virginia, 1972.
J. H. Holland, Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, 1975.
B. Jansen. A note on lower bounds for the QAP, Technical report, Mathematics and Computer Science, Delft University of Technology, The Netherlands, December 1993.
D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, How easy is local search, Journal of Computer and System Sciences 37 , 1988, 79–100.
T. A. Johnson, New linear programming-based solution procedures for the quadratic assignment problem, Ph.D. Thesis, Clemson University, SC, 1992.
M. Jünger, Polyhedral Combinatorics and the Acyclic Subdigraph Problem , Heldermann Verlag, Berlin, Germany, 1985.
M. Jünger and V. Kaibel, A basic study of the QAP polytope, Technical Report 96. 215, Institut für Informatik, Universität zu Köln, Germany, 1996.
M. Jünger and V. Kaibel, On the SQAP polytope, Technical Report 96. 241, Institut für Informatik, Universität zu Köln, Germany, 1996.
V. Kaibel, Polyhedral Combinatorics of the Quadratic Assignment Problem, Ph.D. Thesis, Universität zu Köln, Germany, 1997.
S. E. Karisch, Nonlinear Approaches for Quadratic Assignment and Graph Partition Problems, Ph.D. Thesis , Technical University Graz, Austria, 1995.
S. E. Karisch, E. Çela, J. Clausen, and T. Espersen, A dual framework for lower bounds of the quadratic assignment problem based on linearization, SFB Report 120, Institute of Mathematics, Technical University Graz, Austria, 1997.
S. E. Karisch and F. Rendl, Lower bounds for the quadratic assignment problem via triangle decompositions, Mathematical Programming 71 , 1995, 137–151.
S. E. Karisch, F. Rendl, and H. Wolkowicz, Trust regions and relaxations for the quadratic assignment problem, in Quadratic Assignment and Related Problems , P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 , 1994, 199–220, AMS, Providence, RI.
R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations , R. E. Miller and J. W. Thatcher, eds., Plenum, New York, 1972, 85–103.
L. Kaufmann and Fe Broeckx, An algorithm for the quadratic assignment problem using Benders’ decomposition, European Journal of Operational Research 2 , 1978, 204–211.
B. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Systems Journal 49 , 1972, 291–307.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220 , 1983, 671–680.
J. G. Klincewicz, Avoiding local optima in the p-hub location problem using tabu search and GRASP , Annals of Operations 40 , 1992, 283–302.
J. G. Klincewicz and A. Rajan, Using GRASP to solve the component grouping problem, Technical report, AT&T Bell Laboratories, Holmdel, NJ, 1992.
T. C. Koopmans and M. J. Beckmann, Assignment problems and the location of economic activities, Econometrica 25 , 1957, 53–76.
J. Krarup and P. M. Pruzan, Computer-aided layout design, Mathematical Programming Study 9 , 1978, 75–94.
P. J. M. van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications , D. Reidel Publishing Company, Dordrecht, 1988.
A. M. Land, A problem of assignment with interrelated costs, Operations Research Quarterly 14 , 1963, 185–198.
G. Laporte and H. Mercure, Balancing hydraulic turbine runners: A quadratic assignment problem, European Journal of Operational Research 35 , 1988, 378–382.
E. L. Lawler, The quadratic assignment problem, Management Science 9 , 1963, 586–599.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling Salesman Problem , Wiley, Chichester, 1985.
T. Lengauer, Combinatorial Algorithms for Intergrated Circuit Layout , Wiley, Chichester, 1990.
W. Leontief, Input-Output Economics , Oxford University Press, New York, 1966.
Y. Li and P. M. Pardalos, Generating quadratic assignment test problems with known optimal permutations, Computational Optimization and Applications 1 , 1992, 163–184.
Y. Li, P. M. Pardalos, K. G. Ramakrishnan, and M. G. C. Resende, Lower bounds for the quadratic assignment problem, Annals of Operations Research 50 , 1994, 387–410.
Y. Li, P. M. Pardalos, and M. G. C. Resende, A greedy randomized adaptive search procedure for the quadratic assignment problem, in Quadratic Assignment and Related Problems , P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 1994, 237–261, AMS, Providence, RI.
L. Lovâsz and A. Schrijver, Cones of matrices and set functions and 0–1 optimization, SIAM Journal on Optimization 1 , 1991, 166–190.
E. J. McCormick, Human Factors Engineering , McGraw-Hill, New York, 1970.
T. Magnanti, R. Ahuja, and J. Orlin. Network flows: theory, algorithms, and applications , Prentice Hall, Englewood-Cliffs, New Jersey, 1993.
F. Malucelli, Quadratic Assignment Problems: Solution Methods and Applications, Ph.D. Thesis, Dipartimento di Informatica, Universitâ di Pisa, Italy, 1993.
F. Malucelli and D. Pretolani, Lower bounds for the quadratic semi-assignment problem, Technical Report 955, Centre des Recherches sur les Transports, Université de Montréal, Canada, 1993.
A. Marzetta, Dynamic programming for the quadratic assignment problem, presented at the 2-nd Aussois Workshop on Combinatorial Optimization, 1998, Aussois, France.
T. Mautor and C. Roucairol, A new exact algorithm for the solution of quadratic assignment problems, Discrete Applied Mathematics 55 , 1992, 281–293.
T. Mavridou, P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, A GRASP for the biquadratic assignment problem, European Journal of Operations Research 105 , 1998, 613–621.
N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, Equations of state calculations by fast computing machines, Journal of Chemical Physics 21 , 1953, 1087–1092.
I. Z. Milis and V. F. Magirou, A Lagrangean relaxation algorithm for sparse quadratic assignment problems, Operations Research Letters 17 , 1995, 69–76.
P. B. Mirchandani and T. Obata, Locational decisions with interactions between facilities: the quadratic assignment problem a review, Working Paper Ps-79–1, Rensselaer Polytechnic Institute, Troy, New York, May 1979.
L. Mirsky, The spread of a matrix, Mathematika 3 , 1956, 127–130.
J. Mosevich, Balancing hydraulic turbine runners — a discrete combinatorial optimization problem, European Journal of Operational Research 26 , 1986, 202–204.
K. A. Murthy, P. Pardalos, and Y. Li, A local search algorithm for the quadratic assignment problem, Informatica 3 , 1992, 524–538.
K. G. Murty, An algorithm for ranking all the assignments in order of increasing cost, Operations Research 16 , 1968, 682–287.
H. Müller-Merbach, Optimale Reihenfolgen , Springer-Verlag, Berlin, Heidelberg, New York, 1970, pp. 158–171.
C. E. Nugent, T. E. Vollmann, and J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Journal of Operations Research 16 , 1969, 150–173.
M. W. Padberg and M. P. Rijal, Location , Scheduling , Design and Integer Programming , Kluwer Academic Publishers, Boston, 1996.
Book MATH Google Scholar
M. W. Padberg and G. Rinaldi, Optimization of a 532-city symmetric traveling salesman problem by a branch and cut algorithm, Operations Research Letters 6 , 1987, 1–7.
G. S. Palubeckis, Generation of quadratic assignment test problems with known optimal solutions, U.S.S.R. Comput. Maths. Math. Phys . 28 , 1988, 97–98, (in Russian).
C. H. Papadimitriou and D. Wolfe, The complexity of facets resolved, Proceedings of the 25-th Annual IEEE Symposium on the Foundations of Computer Science (FOCS) , 1985, 74–78.
P. Pardalos and J. Crouse, A parallel algorithm for the quadratic assignment problem, Proceedings of the Supercomputing Conference 1989 , ACM Press, 1989, 351–360.
P. Pardalos, F. Rendl, and H. Wolkowicz, The quadratic assignment problem: A survey and recent developments, in Quadratic Assignment and Related Problems, P. Pardalos and H. Wolkowicz, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 16 , 1994, 1–42, AMS, Providence, RI.
P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, A parallel GRASP implementation for solving the quadratic assignment problem, in Parallel Algorithms for Irregular Problems: State of the Art, A. Ferreira and José D.P. Rolim, eds., Kluwer Academic Publishers, 1995, 115–133.
P. M. Pardalos, L. S. Pitsoulis, and M. G. C. Resende, Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP, ACM Transcations on Mathematical Software 23 , 1997, 196–208.
P. M. Pardalos, K. G. Ramakrishnan, M. G. C. Resende, and Y. Li, Implementation of a variable reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem, SIAM Journal on Optimization 7, 1997, 280–294.
P. M. Pardalos and J. Xue, The maximum clique problem, Research Report 93–1, Department of Industrial and System Engineering, University of Florida, Fl, 1993.
M. Queyranne, Performance ratio of heuristics for triangle inequality quadratic assignment problems, Operations Research Letters 4, 1986, 231–234.
G. Reinelt, The Linear Ordering Problem: Algorithms and Applications , Heldermann Verlag, Berlin, Germany, 1985.
F. Rendl, Ranking scalar products to improve bounds for the quadratic assignment problem, European Journal of Operations Research 20 , 1985, 363–372.
F. Rendl and H. Wolkowicz, Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem, Mathematical Programming 53 , 1992, 63–78.
M. G. C. Resende, P. M. Pardalos, and Y. Li, Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP, ACM Transcations on Mathematical Software 22 , 1996, 104–118.
M. G. C. Resende, L. S. Pitsoulis, and P. M. Pardalos, Approximate solution of weighted max-sat problems using GRASP, in The Satisfiability Problem , P. M. Pardalos, M. G. C. Resende and D. Z. Du, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35 , 1997, 393–405, AMS, Providence, RI.
M. G. C. Resende, K. G. Ramakrishnan, and Z. Drezner, Computing lower bounds for the quadratic assignment problem with an inte-rior point algorithm for linear programming, Operations Research 43 , 1995, 781–791.
W. T. Rhee, A note on asymptotic properties of the quadratic assignment problem, Operations Research Letters 7 , 1988, 197–200.
W. T. Rhee, Stochastic analysis of the quadratic assignment problem, Mathematics of Operations Research 16 , 1991, 223–239.
M. P. Rijal, Scheduling, Design and Assignment Problems with Quadratic Costs, Ph.D . Thesis, New York University, NY, 1995.
C. Roucairol, A reduction method for quadratic assignment problems, Operations Research Verfahren 32 , 1979, 183–187.
C. Roucairol, A parallel branch and bound algorithm for the quadratic assignment problem, Discrete Applied Mathematics 18 , 1987, 221–225.
S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the Association of Computing Machinery 23 , 1976, 555–565.
A. Schäffer and M. Yannakakis, Simple local search problems that are hard to solve, SIAM Journal on Computing 20 , 1991, 56–87.
J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, ORSA Journal on Computing 2 , 1990, 33–45.
J. Skorin-Kapov, Extensions of tabu search adaptation to the quadratic assignment problem, to appear in Computers and Operations Research .
L. Steinberg, The backboard wiring problem: A placement algorithm, SIAM Review 3 , 1961, 37–50.
H. S. Stone, Multiprocessor scheduling with the aid of network flow algorithms, IEEE Transactions on Software Engineering 3 , 1977, 8593.
W. Szpankowski, Combinatorial optimization problems for which almost every algorithm is asymptotically optimall, Optimization 33 , 1995, 359–367.
E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Computing 17 , 1991, 443–455.
D. M. Tate and A. E. Smith, A genetic approach to the quadratic assignment problem, Computers and Operations Research 22 , 1995, 73–83.
I. Ugi, J. Bauer, J. Friedrich, J. Gasteiger, C. Jochum, and W. Schubert, Neue Anwendungsgebiete für Computer in der Chemie, Angewandte Chemie 91 , 1979, 99–111.
D. H. West, Algorithm 608: Approximate solution of the quadratic assignment problem, ACM Transactions on Mathematical Software 9 , 1983, 461–466.
M. R. Wilhelm and T. L. Ward, Solving quadratic assignment problems by simulated annealing, IEEE Transactions 19 , 1987, 107–119.
Q. Zhao, Semidefinite Programming for Assignment and Partitioning Problems, Ph.D . Thesis, University of Waterloo, Ontario, Canada, 1996.
Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz, Semidefinite relaxations for the quadratic assignment problem, Technical Report DIKU TR-96–32, Department of Computer Science, University of Copenhagen, Denmark, 1996. To appear in Journal of Combinatorial Optimization .
Download references
Authors and affiliations.
Institute of Mathematics, Technical University Graz, Steyrergasse 30, 8010, Graz, Austria
Rainer E. Burkard & Eranda Çela
Center for Applied Optimization, Industrial and Systems Engineering Department, University of Florida, Gainesville, FL, 32611, USA
Panos M. Pardalos & Leonidas S. Pitsoulis
You can also search for this author in PubMed Google Scholar
Editors and affiliations.
University of Minnesota, Minneapolis, USA
Ding-Zhu Du
University of Florida, Gainesville, USA
Panos M. Pardalos
Reprints and permissions
© 1998 Kluwer Academic Publishers
Burkard, R.E., Çela, E., Pardalos, P.M., Pitsoulis, L.S. (1998). The Quadratic Assignment Problem. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-0303-9_27
DOI : https://doi.org/10.1007/978-1-4613-0303-9_27
Publisher Name : Springer, Boston, MA
Print ISBN : 978-1-4613-7987-4
Online ISBN : 978-1-4613-0303-9
eBook Packages : Springer Book Archive
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
Policies and ethics
Quadratic assignment problem (QAP) is a fundamental problem in combinatorial optimization and finds numerous applications in operation research, computer vision, and pattern recognition. However, it is a very well-known NP-hard problem to find the global minimizer to the QAP. In this work, we study the semidefinite relaxation (SDR) of the QAP and investigate when the SDR recovers the global minimizer. In particular, we consider the two input matrices satisfy a simple signal-plus-noise model, and show that when the noise is sufficiently smaller than the signal, then the SDR is exact, i.e., it recovers the global minimizer to the QAP. It is worth noting that this sufficient condition is purely algebraic and does not depend on any statistical assumption of the input data. We apply our bound to several statistical models such as correlated Gaussian Wigner model. Despite the sub-optimality in theory under those models, empirical studies show the remarkable performance of the SDR. Our work could be the first step towards a deeper understanding of the SDR exactness for the QAP.
IMAGES
COMMENTS
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 ...
Quadratic Assignment Problem Formulation Parameters = is an n x n matrix where the required flow between facilities and . = is an n x n matrix where the distance between facilities and and . Intuitively, the product of distance and flow represents cost, and the objective is to minimize this cost. ...
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. [1]The problem models the following real-life problem: There are a set of n facilities and a set of n locations.
The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in ... 2.2 Concave Quadratic Formulation In the objective function of (3), let the coefficients cijklbe the entries of an n2 ×n2 matrix S, such that cijkl is on row (i− 1)n+ kand column (j− 1)n+ l. Now let Q:= S− αI,
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 ...
Introduction. The Quadratic Assignment Problem (QAP) is one of the fundamental optimization problems in operations research and has long been challenging to solve, particularly for dynamic, fast-changing scenarios. In this blog post, we demonstrate how we formulated the QAP as a QUBO problem, ran it on the LightSolver platform and benchmarked ...
The quadratic assignment problem (QAP) is considered one of the most difficult optimization problems to solve optimally. The QAP is a combinatorial optimization problem stated for the first time by Koopmans and Beckmann ().Early papers on the subject include Gilmore (), Pierce and Crowston (), Lawler (), and Love and Wong ().The problem is defined as follows.
The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of indivisible economical activities [].Consider the problem of allocating n facilities to n locations, with the cost being a function of the distance and flow between the facilities plus costs associated with placing a facility at a certain location.
The Quadratic Assignment Problem (QAP) has been the subject of an enormous amount of research efforts; ... We present here a generalized formulation of the assignment problem between N objects and M labels, from which most commonly studied variations are special cases. We express all families of assignment problem in this generalized form for ...
The quadratic assignment problem (QAP) was originally introduced in 1957 by Tjalling C. Koopmans and Martin Beckman [26] who were trying to 1. ... 2.2.2 A Quadratic 0-1 Formulation What follows is an equivalent formulation of the QAP as a quadratic 0-1 in-teger program. This formulation was originally used by Koopmans-Beckman
The quadratic assignment problem (QAP) was introduced by Koopmans and Beckman in 1957 in the context of locating "indivisible economic activities". The objective of the problem is to assign a set of facilities to a set of locations in such a way as to minimize the total assignment cost. The assignment cost for a pair of facilities is a ...
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. The main motivation for this survey is the continuous interest in QAP, shown by a number of researchers worldwide ...
The formal definition of the assignment problem (or linear assignment problem) is . Given two sets, A and T, together with a weight function C : A × T → R.Find a bijection f : A → T such that the cost function: (, ())is minimized. Usually the weight function is viewed as a square real-valued matrix C, so that the cost function is written down as: , The problem is "linear" because the cost ...
The quadratic assignment problem (QAP) is a combinatorial optimization problem, that although there is a substantial amount of research devoted to it, it is still, up to this ... The mathematical formulation of this problem leads to an NP-hard anti-Monge-Toeplitz QAP.
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 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. Since algorithms for producing optimal solutions to such problems are computationally infeasible for all but small problems of this type, heuristic techniques must usually ...
#quadraticassignmentproblem #quadratic #assignmentproblem #qapComplete Playlist of Analysis Of Algorithms (DAA):👇👇👇👇👇👇👇👇👇👇👇👇👇 https://www.youtub...
The solution of QAP (F, D) produced by an ǫ-approximation algorithm is called an ǫ-approximate solution. Theorem 3.2 (Sahni and Gonzalez [164], 1976) The quadratic assignment problem is strongly NP-hard. For an arbitrary ǫ > 0, the existence of a polynomial time ǫ-approximation algorithm for the QAP implies P = N P.
This paper surveys some of the most important techniques, applications, and methods regarding the quadratic assignment problem. . Quadratic Assignment Problems model many applications in diverse areas such as operationsresearch, parallel and distributedcomput-ing, and combinatorial data analysis. In this paper we survey some of the most important techniques, applications, and methods regarding ...
The objective of the quadratic assignment problem with flow matrix F and distance matrix D is to find the permutation π0∈ Sn that minimizes the double summation over all i, j. notice that the notation dπ(i)π(j) as above, refers to permuting the rows and columns of the matrix D by some permutation π. That is, Dπ= [ dπ ij ]= dπ(i)π(j ...
Abstract. <P>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.
The quadratic assignment problem (QAP) is a combinatorial optimization problem, that although there is a substantial amount of research devoted to it, it is still, up to this date, not well solvable in the sense that no exact algorithm can solve problems of size n > 20 in reasonable computational time. The QAP can be viewed as a natural extension of the linear assignment problem (LAP; cf. also ...
Quadratic assignment problem (QAP) is a fundamental problem in combinatorial op-timization and finds numerous applications in operation research, computer vision, and ... to improve the formulation in [51], and [10,42] have studied efficient algorithms to solve the SDR. Our work will be more on the theoretical sides of the SDR for QAP.
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]. ... M. S. Bazaraa and H. D. Sherali, Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Research Logistics ...
Quadratic assignment problem (QAP) is a fundamental problem in combinatorial optimization and finds numerous applications in operation research, computer vision, and pattern recognition. However, it is a very well-known NP-hard problem to find the global minimizer to the QAP. In this work, we study the semidefinite relaxation (SDR) of the QAP and investigate when the SDR recovers the global ...