Processing, Please wait...

  • Home
  • About Us
  • Search:
  • Advanced Search

Growing Science » International Journal of Industrial Engineering Computations » How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem

Journals

  • IJIEC (777)
  • MSL (2643)
  • DSL (690)
  • CCL (528)
  • USCM (1092)
  • ESM (421)
  • AC (562)
  • JPM (293)
  • IJDS (952)
  • JFS (101)
  • HE (32)
  • SCI (26)

IJIEC Volumes

    • Volume 1 (17)
      • Issue 1 (9)
      • Issue 2 (8)
    • Volume 2 (68)
      • Issue 1 (12)
      • Issue 2 (20)
      • Issue 3 (20)
      • Issue 4 (16)
    • Volume 3 (76)
      • Issue 1 (9)
      • Issue 2 (15)
      • Issue 3 (20)
      • Issue 4 (12)
      • Issue 5 (20)
    • Volume 4 (50)
      • Issue 1 (14)
      • Issue 2 (10)
      • Issue 3 (12)
      • Issue 4 (14)
    • Volume 5 (47)
      • Issue 1 (13)
      • Issue 2 (12)
      • Issue 3 (12)
      • Issue 4 (10)
    • Volume 6 (39)
      • Issue 1 (7)
      • Issue 2 (12)
      • Issue 3 (10)
      • Issue 4 (10)
    • Volume 7 (47)
      • Issue 1 (10)
      • Issue 2 (14)
      • Issue 3 (10)
      • Issue 4 (13)
    • Volume 8 (30)
      • Issue 1 (9)
      • Issue 2 (7)
      • Issue 3 (8)
      • Issue 4 (6)
    • Volume 9 (32)
      • Issue 1 (9)
      • Issue 2 (6)
      • Issue 3 (7)
      • Issue 4 (10)
    • Volume 10 (34)
      • Issue 1 (8)
      • Issue 2 (10)
      • Issue 3 (8)
      • Issue 4 (8)
    • Volume 11 (36)
      • Issue 1 (9)
      • Issue 2 (8)
      • Issue 3 (9)
      • Issue 4 (10)
    • Volume 12 (29)
      • Issue 1 (9)
      • Issue 2 (6)
      • Issue 3 (8)
      • Issue 4 (6)
    • Volume 13 (41)
      • Issue 1 (10)
      • Issue 2 (8)
      • Issue 3 (10)
      • Issue 4 (13)
    • Volume 14 (50)
      • Issue 1 (11)
      • Issue 2 (15)
      • Issue 3 (9)
      • Issue 4 (15)
    • Volume 15 (55)
      • Issue 1 (19)
      • Issue 2 (15)
      • Issue 3 (12)
      • Issue 4 (9)
    • Volume 16 (75)
      • Issue 1 (12)
      • Issue 2 (15)
      • Issue 3 (19)
      • Issue 4 (29)
    • Volume 17 (51)
      • Issue 1 (21)
      • Issue 2 (30)

Keywords

Supply chain management(168)
Jordan(165)
Vietnam(151)
Customer satisfaction(120)
Performance(115)
Supply chain(112)
Service quality(98)
Competitive advantage(97)
Tehran Stock Exchange(94)
SMEs(89)
optimization(87)
Sustainability(86)
Artificial intelligence(85)
Financial performance(84)
Trust(83)
TOPSIS(83)
Job satisfaction(81)
Genetic Algorithm(78)
Factor analysis(78)
Social media(78)


» Show all keywords

Authors

Naser Azad(82)
Zeplin Jiwa Husada Tarigan(66)
Mohammad Reza Iravani(64)
Endri Endri(45)
Muhammad Alshurideh(42)
Hotlan Siagian(40)
Dmaithan Almajali(37)
Jumadil Saputra(36)
Muhammad Turki Alshurideh(35)
Ahmad Makui(33)
Barween Al Kurdi(32)
Hassan Ghodrati(31)
Basrowi Basrowi(31)
Sautma Ronni Basana(31)
Mohammad Khodaei Valahzaghard(30)
Shankar Chakraborty(29)
Ni Nyoman Kerti Yasa(29)
Haitham M. Alzoubi(28)
Sulieman Ibraheem Shelash Al-Hawary(28)
Prasadja Ricardianto(28)


» Show all authors

Countries

Iran(2192)
Indonesia(1311)
Jordan(813)
India(793)
Vietnam(510)
Saudi Arabia(478)
Malaysia(444)
China(231)
United Arab Emirates(226)
Thailand(160)
United States(114)
Ukraine(110)
Turkey(110)
Egypt(106)
Peru(94)
Canada(93)
Morocco(86)
Pakistan(85)
United Kingdom(80)
Nigeria(78)


» Show all countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print)
Quarterly Publication
Volume 13 Issue 2 pp. 151-164 , 2022

How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem Pages 151-164 Right click to download the paper Download PDF

Authors: Radomil Matousek, Ladislav Dobrovsky, Jakub Kudela

DOI: 10.5267/j.ijiec.2021.12.003

Keywords: Heuristics, Lower bounds, Metaheuristics, Quadratic assignment problem, Starting values

Abstract: The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. The QAP is an NP-hard optimization problem which attracts the use of heuristic or metaheuristic algorithms that can find quality solutions in an acceptable computation time. On the other hand, there is quite a broad spectrum of mathematical programming techniques that were developed for finding the lower bounds for the QAP. This paper presents a fusion of the two approaches whereby the solutions from the computations of the lower bounds are used as the starting points for a metaheuristic, called HC12, which is implemented on a GPU CUDA platform. We perform extensive computational experiments that demonstrate that the use of these lower bounding techniques for the construction of the starting points has a significant impact on the quality of the resulting solutions.


How to cite this paper
Matousek, R., Dobrovsky, L & Kudela, J. (2022). How to start a heuristic? Utilizing lower bounds for solving the quadratic assignment problem.International Journal of Industrial Engineering Computations , 13(2), 151-164.

Refrences
Abdel-Basset, M., Manogaran, G., El-Shahat, D., & Mirjalili, S. (2018). Integrating the whale algorithm with Tabu search for quadratic assignment problem: A new approach for locating hospital departments. Applied soft computing, 73, 530-546.
Adams, W. P., & Johnson, T. A. (1994). Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS series in discrete mathematics and theoretical computer science, 16, 43-77.
Adams, W. P., Guignard, M., Hahn, P. M., & Hightower, W. L. (2007). A level-2 reformulation–linearization technique bound for the quadratic assignment problem. European Journal of Operational Research, 180(3), 983-996.
Ahmed, Z. H. (2015). A multi-parent genetic algorithm for the quadratic assignment problem. Opsearch, 52(4), 714-732.
Aksan, Y., Dokeroglu, T., & Cosar, A. (2017). A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem. Computers & Industrial Engineering, 103, 105-115.
Anstreicher, K. M., & Brixius, N. W. (2001). A new bound for the quadratic assignment problem based on convex quadratic programming. Mathematical Programming, 89(3), 341-357.
Anstreicher, K. M. (2003). Recent advances in the solution of quadratic assignment problems. Mathematical Programming, 97(1), 27-42.
Benlic, U., & Hao, J. K. (2015). Memetic search for the quadratic assignment problem. Expert Systems with Applications, 42(1), 584-595.
Burkard, R. E., & Rendl, F. (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operational Research, 17(2), 169-174.
Burkard, R. E., Karisch, S. E., & Rendl, F. (1997). QAPLIB–a quadratic assignment problem library. Journal of Global optimization, 10(4), 391-403.
Burkard, R. E., Dell'Amico, M., & Martello, S. (2012). Assignment problems: revised reprint. Society for Industrial and Applied Mathematics.
Cela, E. (2013). The quadratic assignment problem: theory and algorithms (Vol. 1). Springer Science & Business Media.
Cela, E., Deineko, V., & Woeginger, G. J. (2018). New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices. European journal of operational research, 267(3), 818-834.
Chmiel, W., & Szwed, P. (2016). Bees algorithm for the quadratic assignment problem on CUDA platform. In Man–Machine Interactions 4 (pp. 615-625). Springer, Cham.
Czapiński, M. (2013). An effective parallel multistart tabu search for quadratic assignment problem on CUDA platform. Journal of Parallel and Distributed Computing, 73(11), 1461-1468.
de Klerk, E., & Sotirov, R. (2012). Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Mathematical programming, 133(1), 75-91.
Dell’Amico, M., Diaz, J. C. D., Iori, M., & Montanari, R. (2009). The single-finger keyboard layout problem. Computers & Operations Research, 36(11), 3002-3012.
Dickey, J. W., & Hopkins, J. W. (1972). Campus building arrangement using TOPAZ. Transportation Research, 6(1), 59-68.
Dokeroglu, T. (2015). Hybrid teaching–learning-based optimization algorithms for the quadratic assignment problem. Computers & Industrial Engineering, 85, 86-101.
Dokeroglu, T., & Cosar, A. (2016). A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem. Engineering Applications of Artificial Intelligence, 52, 10-25.
Eschermann, B., & Wunderlich, H. J. (1990). Optimized synthesis of self-testable finite state machines. In 20th international symposium on fault-tolerant computing (FTCS 20).
Fischetti, M., Monaci, M., & Salvagnin, D. (2012). Three ideas for the quadratic assignment problem. Operations research, 60(4), 954-964.
Fleurent, C., & Ferland, J. A. (1994). Genetic hybrids for the quadratic assignment problem. Quadratic assignment and related problems, 16, 173-187.
Gilmore, P. C. (1962). Optimal and suboptimal algorithms for the quadratic assignment problem. Journal of the society for industrial and applied mathematics, 10(2), 305-313.
Hadley, S. W., Rendl, F., & Wolkowicz, H. (1992). A new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17(3), 727-739.
Hafiz, F., & Abdennour, A. (2016). Particle Swarm Algorithm variants for the Quadratic Assignment Problems-A probabilistic learning approach. Expert Systems with Applications, 44, 413-431.
Haghani, A., & Chen, M. C. (1998). Optimizing gate assignments at airport terminals. Transportation Research Part A: Policy and Practice, 32(6), 437-454.
Hahn, P. M., Zhu, Y. R., Guignard, M., Hightower, W. L., & Saltzman, M. J. (2012). A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS Journal on Computing, 24(2), 202-209.
Hameed, A., Aboobaider, B., Mutar, M., & Choon, N. (2020). A new hybrid approach based on discrete differential evolution algorithm to enhancement solutions of quadratic assignment problem. International Journal of Industrial Engineering Computations, 11(1), 51-72.
Harris, M., Berretta, R., Inostroza-Ponta, M., & Moscato, P. (2015, May). A memetic algorithm for the quadratic assignment problem with parallel local search. In 2015 IEEE congress on evolutionary computation (CEC) (pp. 838-845). IEEE.
Helber, S., Böhme, D., Oucherif, F., Lagershausen, S., & Kasper, S. (2016). A hierarchical facility layout planning approach for large and complex hospitals. Flexible services and manufacturing journal, 28(1), 5-29.
Hoffman, A. J., & Wielandt, H. W. (2003). The variation of the spectrum of a normal matrix. In Selected Papers Of Alan J Hoffman: With Commentary (pp. 118-120).
Hubert, L., & Schultz, J. (1976). Quadratic assignment as a general data analysis strategy. British journal of mathematical and statistical psychology, 29(2), 190-241.
Hussin, M. S., & Stützle, T. (2014). Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances. Computers & operations research, 43, 286-291.
Kaufman, L., & Broeckx, F. (1978). An algorithm for the quadratic assignment problem using Bender's decomposition. European Journal of Operational Research, 2(3), 207-211.
Karisch, S. E., Cela, E., Clausen, J., & Espersen, T. (1999). A dual framework for lower bounds of the quadratic assignment problem based on linearization. Computing, 63(4), 351-403.
Koopmans, T. C., & Beckmann, M. (1957). Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, 53-76.
Matousek, R., & Zampachova, E. (2011). Promising GAHC and HC12 algorithms in global optimization tasks. Optimization methods and software, 26(3), 405-419.
Matousek, R., Popela, P., & Kudela, J. (2017). Heuristic approaches to stochastic quadratic assignment problem: Var and cvar cases. Mendel, 23(1), 73-78.
Matousek, R., Dobrovsky, L., & Kudela, J. (2019, July). The quadratic assignment problem: metaheuristic optimization using HC12 algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 153-154).
Mohammadi, J., Mirzaie, K., & Derhami, V. (2015, November). Parallel genetic algorithm based on GPU for solving quadratic assignment problem. In 2015 2nd International Conference on Knowledge-Based Engineering and Innovation (KBEI) (pp. 569-572). IEEE.
Laporte, G., & Mercure, H. (1988). Balancing hydraulic turbine runners: A quadratic assignment problem. European Journal of Operational Research, 35(3), 378-381.
Lawler, E. L. (1963). The quadratic assignment problem. Management science, 9(4), 586-599.
Li, Y., & Pardalos, P. M. (1992). Generating quadratic assignment test problems with known optimal permutations. Computational Optimization and Applications, 1(2), 163-184.
Peng, J., Mittelmann, H., & Li, X. (2010). A new relaxation framework for quadratic assignment problems based on matrix splitting. Mathematical Programming Computation, 2(1), 59-77.
Peng, J., Zhu, T., Luo, H., & Toh, K. C. (2015). Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting. Computational Optimization and Applications, 60(1), 171-198.
Popela, P., Matousek, R., & Kudela, J. (2016). Heuristic approaches to stochastic quadratic assignment problem: VO and MM cases. Mendel 22(1), 117-122.
Samanta, S., Philip, D., & Chakraborty, S. (2018). Bi-objective dependent location quadratic assignment problem: Formulation and solution using a modified artificial bee colony algorithm. Computers & Industrial Engineering, 121, 8-26.
Sanhueza, C., Jiménez, F., Berretta, R., & Moscato, P. (2017, June). PasMoQAP: a parallel asynchronous memetic algorithm for solving the multi-objective quadratic assignment problem. In 2017 IEEE congress on evolutionary computation (CEC) (pp. 1103-1110). IEEE.
Steinberg, L. (1961). The backboard wiring problem: A placement algorithm. Siam Review, 3(1), 37-50.
Taillard, É. (1991). Robust taboo search for the quadratic assignment problem. Parallel computing, 17(4-5), 443-455.
Tosun, U. (2015). On the performance of parallel hybrid algorithms for the solution of the quadratic assignment problem. Engineering applications of artificial intelligence, 39, 267-278.
Tsutsui, S., & Fujimoto, N. (2009, July). Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (pp. 2523-2530).
Xia, Y., & Yuan, Y. X. (2006). A new linearization method for quadratic assignment problems. Optimisation Methods and Software, 21(5), 805-818.
Zhang, H., Beltran-Royo, C., & Ma, L. (2013). Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers. Annals of Operations Research, 207(1), 261-278.
Zhao, Q., Karisch, S. E., Rendl, F., & Wolkowicz, H. (1998). Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2(1), 71-109.
  • 51
  • 1
  • 2
  • 3
  • 4
  • 5

Journal: International Journal of Industrial Engineering Computations | Year: 2022 | Volume: 13 | Issue: 2 | Views: 2159 | Reviews: 0

Related Articles:
  • A new hybrid approach based on discrete differential evolution algorithm to ...
  • Development of modified discrete particle swarm optimization algorithm for ...
  • An approach for solving multi-objective assignment problem with interval pa ...
  • A hybrid Tabu search-simulated annealing method to solve quadratic assignme ...
  • Two models for the generalized assignment problem in uncertain environment

Add Reviews

Name:*
E-Mail:
Review:
Bold Italic Underline Strike | Align left Center Align right | Insert smilies Insert link URLInsert protected URL Select color | Add Hidden Text Insert Quote Convert selected text from selection to Cyrillic (Russian) alphabet Insert spoiler
winkwinkedsmileam
belayfeelfellowlaughing
lollovenorecourse
requestsadtonguewassat
cryingwhatbullyangry
Security Code: *
Include security image CAPCHA.
Refresh Code

® 2010-2026 GrowingScience.Com