Received 23.04.2024; Revised 02.06.2024; Accepted 10.09.2024

Published 24.09.2024; First Online 30.09.2024

https://doi.org/10.34229/2707-451X.24.3.3

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

UDC 519.854

Algorithm Portfolios for Solving the Quadratic Assignment Problem

Ivan Sergienko ,   Volodymyr Shylo,   Valentyna Roshchyn,   Petro Shylo ^*,   Dmytro Boyarchuk,   Valerii Moroz

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. The quadratic assignment problem is a well-established NP-hard problem in combinatorial optimization with applications in diverse fields like economics, archaeology, and chemistry. Due to its complexity, research on efficient solution methods remains active, including efforts for parallelization on multiprocessor computing systems. However, effective parallel algorithms are crucial to fully leverage these computational resources. In this context, algorithm unions (portfolios and teams) play a significant role in achieving parallel execution for solving such problems.

Research objectives. This work investigates the application of portfolios constructed from modifications of the repeated iterated tabu search algorithm to the quadratic assignment problem. The effectiveness of these portfolios was evaluated through experimental computations.

Results. The portfolios, derived from modifications of the repeated iterated tabu search algorithm, were applied to the quadratic assignment problem. For the most demanding test instances, the proposed algorithms were evaluated on the SCIT-4 supercomputer, alongside previously published results from the authors, confirming their competitive performance. Additionally, we assessed the parallel efficiency of these portfolios in solving instances of the quadratic assignment problem. The results demonstrate their ability to accelerate the optimization process (with speedup dependent on problem size and utilized processors), enabling the solution of large-scale problems.

Conclusions. The conducted studies demonstrate that employing algorithm portfolios significantly accelerates the solution process for the quadratic assignment problem. Analysis of the results reveals a near-linear speedup factor achieved by the portfolio. For the challenging test instance tai100a, a new best solution value of 21040996 was obtained using a portfolio of 16 algorithms.

 

Keywords: quadratic assignment problem, algorithm portfolios, experimental research, algorithm portfolios efficiency.

 

Cite as: Sergienko I., Shylo V., Roshchyn V., Shylo P., Boyarchuk D., Moroz V. Algorithm Portfolios for Solving the Quadratic Assignment Problem. Cybernetics and Computer Technologies. 2024. 3. P. 25–33. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.3.3

 

References

           1.     Misevicius A. An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectrum. 2012. Vol. 34, N. 3. P. 665–690. https://doi.org/10.1007/s00291-011-0274-z

           2.     Benlic U., Hao J.K. Memetic search for the quadratic assignment problem. Expert Systems with Applications. 2015. Vol. 42, N. 1. P. 584–595. https://doi.org/10.1016/j.eswa.2014.08.011

           3.     Shylo P.V. Solving the Quadratic Assignment Problem by the Repeated Iterated Tabu Search Method. Cybern. Syst. Analysis. 2017. Vol. 53. P. 308–311. https://doi.org/10.1007/s10559-017-9930-x

           4.     Misevičius A. New best known solution for the most difficult QAP instance “tai100a”. Memetic Computing. 2019. Vol. 11, N. 3. P. 331–332. https://doi.org/10.1007/s12293-019-00289-y

           5.     Yangming Z., Hao J.K., Duval B. Frequent Pattern Based Search: A Case Study on the Quadratic Assignment Problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2020. Vol. 52. P. 1503–1515. http://dx.doi.org/10.1109/TSMC.2020.3027860

           6.     Sergienko I.V., Shylo V.P., Chupov S.V., Shylo P.V. Solving the Quadratic Assignment Problem. Cybern. Syst. Analysis. 2020. Vol. 56. P. 53–57. https://doi.org/10.1007/s10559-020-00219-8

           7.     Misevičius A., Verenė D. A hybrid genetic-hierarchical algorithm for the quadratic assignment problem. Entropy. 2021.Vol. 23, N. 1. P 108. https://doi.org/10.3390/e23010108

           8.     Wang H., Alidaee B. A New Hybrid-heuristic for Large-scale Combinatorial Optimization: A Case of Quadratic Assignment Problem. Computers & Industrial Engineering. 2023. Vol. 179. https://doi.org/10.1016/j.cie.2023.109220

           9.     Shylo V.P., Glover F., Sergienko I.V. Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Cybern. Syst. Analysis. 2015. Vol. 51. P. 16–24. https://doi.org/10.1007/s10559-015-9692-2

       10.     Sergienko I.V., Shylo V.P., Roshchyn V.O. Discrete optimization. Algorithms and their effective use. Kyiv: Naukova dumka, 2020. 144 p. (in Ukrainian)

       11.     Sergienko I.V., Shylo V.P., Roshchyn V.O. Algorithm Unions for Solving Discrete Optimization Problems. Cybern Syst. Analysis. 2023. Vol. 59. P. 753–762. https://doi.org/10.1007/s10559-023-00611-0

       12.     Sergienko I.V., Shylo V.P. Kernel technology to solve discrete optimization problems. Cybern. Syst. Analysis. 2017. Vol. 53. P. 884–892. https://doi.org/10.1007/s10559-017-9990-y

       13.     Taillard E. Robust taboo search for the quadratic assignment problem. Parallel Computing. 1991. Vol. 17, Iss. 4–5. P. 443–455. https://doi.org/10.1016/S0167-8191(05)80147-4

       14.     Golovynskyi А.L., Malenko А.L., Sergienko І.V., Tulchinsky В.H. Power Efficient Supercomputer SCIT-4. Visn. Nac. Akad. Nauk Ukr. 2013. N. 2. P. 50–59. (in Ukrainian) https://doi.org/10.15407/visn2013.02.050

       15.     Shylo V.P., Chupov, S.V. Parallel approximate algorithms for solving the quadratic assignment problem. International scientific symposium “Intelligent solutions”. Decision theory: proceedings, international school-seminar (15–20 April 2019, Uzhhorod). Uzhhorod: Invazor, 2019. P. 131, 132. (in Ukrainian)

       16.     Sergienko I.V., Shylo V.P. Discrete optimization problems: problems, solution methods, studies. Kyiv: Naukova dumka. 2003. 264 p. (in Russian)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next