Research Article

A Survey of Quadratic Assignment Problems

by  Abdel Nasser H. Zaied, Laila Abd El-Fatah Shawky
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 101 - Issue 6
Published: September 2014
Authors: Abdel Nasser H. Zaied, Laila Abd El-Fatah Shawky
10.5120/17693-8662
PDF

Abdel Nasser H. Zaied, Laila Abd El-Fatah Shawky . A Survey of Quadratic Assignment Problems. International Journal of Computer Applications. 101, 6 (September 2014), 28-36. DOI=10.5120/17693-8662 

                        @article{ 10.5120/17693-8662,
                        author  = { Abdel Nasser H. Zaied,Laila Abd El-Fatah Shawky },
                        title   = { A Survey of Quadratic Assignment Problems },
                        journal = { International Journal of Computer Applications },
                        year    = { 2014 },
                        volume  = { 101 },
                        number  = { 6 },
                        pages   = { 28-36 },
                        doi     = { 10.5120/17693-8662 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2014
                        %A Abdel Nasser H. Zaied
                        %A Laila Abd El-Fatah Shawky
                        %T A Survey of Quadratic Assignment Problems%T 
                        %J International Journal of Computer Applications
                        %V 101
                        %N 6
                        %P 28-36
                        %R 10.5120/17693-8662
                        %I Foundation of Computer Science (FCS), NY, USA
Abstract

The quadratic assignment problem (QAP) is very challengeable and interesting problem that can model many real-life problems. In this paper, we will simply discuss the meaning of quadratic assignment problem, solving techniques and we will give a survey of some developments and researches.

References
  • E. M. Loiola, N. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, T. Querido. A survey for the quadratic assignment problem. European journal of operational research, 27 December 2005.
  • Quadratic Assignment Problem. (2012). retrieved May 2014 , from: http://www. neos-guide. org/content/quadratic-assignment-problem
  • QAPLIB - A Quadratic Assignment Problem Library. (2012). Retrieved May 2014, from: http://www. seas. upenn. edu/qaplib
  • P. Ji, Y. Wu, H. Liu. A Solution Method for the Quadratic Assignment Problem (QAP), Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong ,China, August 2006.
  • Quadratic assignment problem. (2013). Retrieved May 2014, from: http://en. wikipedia. org/wiki/Quadratic_assignment_problem
  • I. Kudelska . Methods of using the quadratic assignment problem solution, LogForum 8, Issue 3, 2012.
  • Assignment problem (2014). Retrieved May 2014, from: http://en. wikipedia. org/wiki/Assignment_problem
  • T. Stützle. Iterated local search for the quadratic assignment problem, European Journal of Operational Research , Volume 174, Issue 3, 1 November 2006.
  • Z. Wu, Y. Yang, F. Bai, J. Tian. Global optimality conditions and optimization methods for quadratic assignment problems , Volume 218, Issue 11, 5 February 2012.
  • E. Duman, M. Uysal, A. F. Alkaya. Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem, Information Sciences, Volume 217, 25 December 2012.
  • U. Benlic, J. Hao. Breakout local search for the quadratic assignment problem, Applied Mathematics and Computation, Volume 219, Issue 9, 1 January 2013.
  • E. . Klerk, M. Nagy, R. Sotirov, U. Truetsch. Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, European Journal of Operational Research, Volume 233, Issue 3, 16 March 2014.
  • Y. Xia, and Y. Yuan. A new linearization method for quadratic assignment problems, Institute of Computational Mathematics and Scientific/Engineering Computing,The Academy of Mathematics and Systems Sciences,Chinese Academy of Sciences, Beijing, China.
  • R. E. Burkard , E. Cela ,P. M. Pardalos , and L. S. Pitsoulis. The Quadratic Assignment Problem, Handbook of combinatorial optimization, 1998.
  • C. W. Commander. A Survey of the Quadratic Assignment Problem, with Applications, Morehead Electronic Journal of Applicable Mathematics, Issue 4,1 March 2005.
  • N. W. Brixius and K. M. Anstreicher. The Steinberg wiring problem. Working Paper, The University of Iowa, October 2001.
  • A. N. Elshafei. Hospital layout as a quadratic assignment problem, Operational Research Quarterly, 1977.
  • Juillet. comparison of iterative searches for the quadratic assignment problem, Montréal university, Canada,1994.
  • E. M. Loiola, N. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido. A survey for the quadratic assignment problem, European Journal of Operational Research, 27 December 2005.
  • F. D. Fomeni. New Solution Approaches for the Quadratic Assignment Problem, University of the Witwatersrand, Johannesburg, September 2011.
  • R. K. Ahuja, K. C. Jha, J. B. Orlin and D. Sharma. Very large-scale neighborhood search for the quadratic assignment problem, Working Paper, MIT Sloan School of Management, July 2002.
  • N. Christofides and E. Benavent. An exact algorithm for the quadratic assignment problem on a tree, Operation Research, 1989.
  • E. -G. Talbi , O. Roux, C. Fonlupt, and D. Robillard. Parallel Ant Colonies for the quadratic assignment problem. Future Generation Computer Systems , Volume 17 ,France, 2001.
  • M. Dorigo. Optimization, learning and natural algorithms, Ph. D. Thesis, Politecnico di Milano, Italy, 1992.
  • A. kaveh. Algorithms and theoretical topics on selected combinatorial optimization problems. Simon fraser university,2006.
  • T. C. Koopmans and M. Beckman. Assignment Problems and the Location of Economic Activities. Econometric ,1957.
  • Hanan, M. and J. M. Kurtzberg . A Review of the Placement and Quadratic Assignment Problems, 1972.
  • Sahni, S. and T. Gonzalez. P-Complete Aproximation Problems. Journal of the ACM ,1976.
  • P. C. Gilmore . Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem. SIAM Journal on Applied Mathematics , Volume 10, 1962.
  • E. L. Lawler. The Quadratic Assignment Problem, Management Science, Volume 9, 1963.
  • M. S. Hussin and T. Stutzle. Hierarchical Iterated Local Search for the Quadratic Assignment Problem, Institut de Recherches Interdisciplinaires, et de D´eveloppements en Intelligence Artificielle, Universite Libre de Bruxelles, Bruxelles, Belgium, June 2009.
  • F. Rendl and H. Wolkowicz . Applications of Parametric Programming and Eigenvalue Maximization to the Quadratic Assignment Problem. Mathematical Programming , Volume 53, 1992.
  • P. . M. Zvidrezner , and E. D. Taillard. Recent Advances for the Quadratic Assignment Problem with Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods. Annals of Operations Research , Volume 139, 2005.
  • P. Carraresi, and F. Malucelli. A New Lower Bound for the Quadratic Assignment Problem. Tech Report TR-34/92, Universita di Pisa, 1992.
  • M. Dell'Amico, J. Carlos D´?az , M. Iori and R. Montanari . The single-finger keyboard layout problem. University of Modena and Reggio Emilia, Italy, November 2008.
  • P. M. Pardalos, F. Rendl, and H. Wolkowicz. The Quadratic Assignment Problem: A Survey and Recent Developments, in Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 16, 1994.
  • P. Hahn, T. Grant, and N. Hall. A Branch-and-Bound Algorithm for the Quadratic Assignment Problem Based on the Hungarian Method, European Journal of Operational Research, 1996.
  • M. S. Bazaraa and H. D. Sherali. On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem . The Journal of the Operational Research Society, Volume 33, Issue 11, Novmber 1982.
  • G. Erdo?an. quadratic assignment problem:linearizations and polynomial time solvable cases. October, 2006.
  • R. Bellman, An introduction to the theory of dynamic programming, 1953.
  • Francesco. A Bandit-Inspired Memetic Algorithm for Quadratic Assignment Problems. University of Utrecht. August 2012.
  • E. Cela. Assignment Problems . Technical University Graz, Institute of Mathematics,Steyrergasse 30, A-8010 Graz, Austria.
  • G. C. Armour, and E. S. Buffa. Heuristic Algorithm and Simulation Approach to Relative Location of Facilities. Management Science, Volume 9, 1963.
  • Y. Li, P. M. Pardalos, and M. G. C. Resende. A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
  • B. Vahedinori, M. Kianpour and P. Fattahi. Using Greedy Randomize Adaptive Search Procedure for solve the Quadratic Assignment Problem, Volume 22, November 2011.
  • H. M. Nehi, and S. Gelareh. A Survey of Meta-Heuristic Solution Methods for the Quadratic Assignment Problem. Applied Mathematical Sciences, Volume 1, Issue 46, 2007.
Index Terms
Computer Science
Information Sciences
No index terms available.
Keywords

Quadratic Assignment Problem formulation Exact Algorithm NP-complete Bound Heuristic.

Powered by PhDFocusTM