Review on the Methods to Solve Combinatorial Optimization Problems Particularly: Quadratic Assignment Model

  • Authors

    • Asaad Shakir Hameed
    • Burhanuddin Mohd Aboobaider
    • Ngo Hea Choon
    • Modhi Lafta Mutar
    • Wassim Habib Bilal
    2018-09-01
    https://doi.org/10.14419/ijet.v7i3.20.18722
  • Quadratic Assignment Problem, Metaheuristic Algorithms, Combinatorial Optimization Problems.

  • Abstract

    The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problem (COPs) in the branch of optimization or operation research in mathematics, from the category of the Facilities Location Problems (FLPs).  The quadratic assignment problem (QAP) be appropriate to the group of NP-hard issues and is measured as a challenging problem of the combinatorial optimization. QAP in Location Theory considers one of the problems of facilities tracing which the rate of locating a facility be determined by the spaces between facilities as well as the communication among the further facilities. QAP was presented in 1957 by Beckman and Koopmans as they were attempting to model a problem of facilities location. To survey the researcher’s works for QAP and applied, the mapped research landscape outlines literature into a logical classification and discovers this field basic characteristics represented on the motivation to use the quadratic assignment problem applied in hospital layout and campus planning. This survey achieved a concentrated each QAP article search in three key databases: Web of Science, Science Direct, and IEEE Xplore. Those databases are regarded extensive adequate in covering QAP and the methods utilized in solving QAP.

     

  • References

    1. [1] W. R. P. and A. S. ا. William H. Cunningham, “Combinatorial Optimization by,†Int. J. Numer. Model., vol. 11 (1998) 273–274.

      [2] R. K. Bhati and A. Rasool, “Quadratic Assignment Problem and its Relevance to the Real World: A Survey,†Int. J. Comput. Appl., vol. 96, no. 9 (2014) 42–47.

      [3] S. Sahni and T. Gonzalez, “P-Complete Approximation Problems,†J. ACM, vol. 23, no. 3 (1976) 555–565.

      1. D. Gonçalves, A. A. Pessoa, C. Bentes, R. Farias, and L. M. de A. Drummond, “A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique,†INFORMS J. Comput., vol. 29, no. 4 (2017) 676–687.

      [4] W. Chmiel, P. Kadłuczka, J. Kwiecień, and B. Filipowicz, “A comparison of nature inspired algorithms for the quadratic assignment problem,†Bull. Polish Acad. Sci. Tech. Sci., vol. 65, no. 4 (2017) 513–522.

      [5] M. Abdel-Baset, H. Wu, Y. Zhou, and L. Abdel-Fatah, “Elite opposition-flower pollination algorithm for quadratic assignment problem,†J. Intell. Fuzzy Syst., vol. 33, no. 2 (2017) 901–911.

      [6] T. C. Koopmans and M. J. Beckmann, “Assignment Problems and the Location of Economic Activities Author ( s ): Tjalling C . Koopmans and Martin Beckmann,†Econometrica, vol. 25, no. 1 (1957) 53–76.

      [7] M. Bayat and M. Sedghi, Quadratic Assignment Problem. 2009.

      [8] E. Duman, M. Uysal, and A. F. Alkaya, “Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem,†Inf. Sci. (Ny)., vol. 217 (2012) 65–77.

      [9] U. Benlic and J. K. Hao, “Breakout local search for the quadratic assignment problem,†Appl. Math. Comput., vol. 219, no. 9 (2013) 4800–4815.

      [10] B. R. M. M. Y. Mohamad Amin Kaviani, Mehdi Abbasi, “A hybrid Tabu search-simulated annealing method to solve quadratic assignment problem,†Decis. Sci. Lett., vol. 3, no. 3 (2014) 391–396.

      1. R. Montero and A. S. Lopez, “Ant Colony Optimization for Solving the Quadratic Assignment Problem,†2015 Fourteenth Mex. Int. Conf. Artif. Intell., no. 3 (2015) 182–187.

      [11] E. Lalla-Ruiz, C. Expósito-Izquierdo, B. Melián-Batista, and J. M. Moreno-Vega, “A Hybrid Biased Random Key Genetic Algorithm for the Quadratic Assignment Problem,†Inf. Process. Lett., vol. 116, no. 8 (2016) 513–520.

      [12] S. S. Syed-Abdullah, S. Abdul-Rahman, A. M. Benjamin, A. Wibowo, and K.-R. Ku-Mahamud, “Solving Quadratic Assignment Problem with Fixed Assignment (QAPFA) using Branch and Bound Approach,†IOP Conf. Ser. Mater. Sci. Eng., vol. 300 (2018).

      [13] E. M. Loiola, N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, “A survey for the quadratic assignment problem,†Eur. J. Oper. Res., vol. 176, no. 2 (2007) 657–690.

      [14] Leon Steiberg, “THE BACKBOARD WIRING PROBLEM: A PLACEMENT ALGORITHM,†vol. 3, no. 1 (1961) 37–50.

      [15] J. W. Dickey and J. W. Hopkins, “Campus building arrangement using topaz,†Transp. Res., vol. 6, no. 1 (1972) 59–68.

      [16] Heffley, “The Quadratic Assignment Problem : A Note Author ( s ): Dennis R . Heffley Published by : The Econometric Society Stable URL : http://www.jstor.org/stable/1913863 Accessed : 12-05-2016 16 : 27 UTC Your use of the JSTOR archive indicates your acceptance of,†vol. 40, no. 6 (1972) 1155–1163.

      [17] J. Krarup and P. M. Pruzan, “COMPUTER.AIDED LAYOUT DESIGN,†vol. 9 (1978).

      [18] S. Benjaafar, “Modeling and Analysis of Congestion in the Design of Facility Layouts,†Manage. Sci., vol. 48, no. 5 (2002) 679–704.

      [19] G. Ben-David and D. Malah, “Bounds on the performance of vector-quantizers under channel errors,†IEEE Trans. Inf. Theory, vol. 51, no. 6 (2005) 2227–2235.

      [20] C. J. and Rahmann, Comparative Analysis of Cyclic Sequences: Viroids and other Small Circular RNAs. 2006.

      [21] M. D. Amico, “The single-finger keyboard layout problem,†Comput. Oper. Res., vol. 11 (2009) 3002–3012.

      [22] X. Feng and Q. Su, “An applied case of quadratic assignment problem in hospital department layout,†2015 12th Int. Conf. Serv. Syst. Serv. Manag. ICSSSM 2015, 2015.

      [23] N. Christofides and E. Benavent, “An Exact Algorithm for the Quadratic Assignment Problem on a Tree,†vol. 37, no. 5 (1989) 760–768.

      [24] M. S. Bazaraa and H. D. Sherali, “On the use of exact and heuristic cutting plane methods for the quadratic assignment problem,†J. Oper. Res. Soc., vol. 33, no. 11 (1982) 991–1003.

      [25] M. S. Bazaraa and O. Kirca, “A Branch-and-Bound-Based Heuristic for Solving the Quadratic Assignment Problem,†Nav. Reserach Logist. Q., vol. 30 (1983) 287–304.

      1. F. E. O. Thomas, “A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM,†vol. 8, no. April (1989) 67–71.

      [26] F. Glover, “Tabu Search - Part I.,†ORSA J. Comput. 1, vol. 1, no. 3 (1989) 190–206.

      [27] N. Mladenović and P. Hansen, “Variable neighborhood search,†Comput. Oper. Res., vol. 24, no. 11(1997) 1097–1100.

      [28] M. R. Wilhelm and T. L. Ward, “Solving Quadratic Assignment Problems by ‘Simulated Annealing,’†IIE Trans., vol. 19, no. 1(1987) 107–119.

      1. S. Ramkumar, S. G. Ponnambalam, N. Jawahar, and R. K. Suresh, “Iterated fast local search algorithm for solving quadratic assignment problems,†Robot. Comput. Integr. Manuf., vol. 24, no. 3(2008) 392–401.

      [29] Colorni, M. Dorigo, and V. Maniezzo, “An Investigation of some Properties of an``Ant Algorithm’’.,†Ppsn, no. Ppsn 92 (1992) 2–7.

      [30] D. KARABOGA, “AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION,†Decis. Support Syst. (2005) 1–10.

      [31] J. Wen, H. Ma, and X. Zhang, “Optimization of the occlusion strategy in visual tracking,†Tsinghua Sci. Technol., vol. 21, no. 2 (2016) 221–230.

      [32] X.-S. Yang and S. Deb, “Cuckoo Search via Levy Flights,†(2010) 1–7.

      [33] X.-S. Yang, Genetic Algorithms. Nature-Inspired Optimization Algorithms (2014).

      [34] M. E. Riffi, Y. Saji, and M. Barkatou, “Incorporating a modified uniform crossover and 2-exchange neighborhood mechanism in a discrete bat algorithm to solve the quadratic assignment problem Incorporating a modified uniform crossover and 2-exchange neighborhood mechanism,†Egypt. Informatics J., vol. 18, no. 3(2017) 221–232.

      [35] T. G. Crainic and M. Toulouse, “Parallel strategies for meta-heuristics,†in Handbook of metaheuristics, Springer, (2003) 475–513.

      [36] E.-G. Talbi, Studies in Computational Intelligence. 2013.

  • Downloads

  • How to Cite

    Shakir Hameed, A., Mohd Aboobaider, B., Hea Choon, N., Lafta Mutar, M., & Habib Bilal, W. (2018). Review on the Methods to Solve Combinatorial Optimization Problems Particularly: Quadratic Assignment Model. International Journal of Engineering & Technology, 7(3.20), 15-20. https://doi.org/10.14419/ijet.v7i3.20.18722

    Received date: 2018-09-01

    Accepted date: 2018-09-01

    Published date: 2018-09-01