Оптимізація обчислень в алгоритмах мультиплексного розбиття континуальних множин

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2025.46(1).195-208

Ключові слова:

мультиплексне розбиття, оптимізація, мемоізація, векторизація, SIMD-інструкції

Анотація

У роботі представлено розробку та оптимізацію алгоритмів для розв’язання задач мультиплексного розбиття множин із використанням методів векторизації обчислень. Здійснено порівняння базового ітеративного підходу із векторизованим методом, що також включає попереднє обчислення тензора відстаней між точками та центрами. Використання SIMD-інструкцій дозволило значно скоротити час виконання обчислень та підвищити продуктивність алгоритму. Результати підтверджують ефективність застосованих методів для задач із великими обсягами даних.

Біографія автора

Д. Є. Лубенець, Нацiональний технiчний унiверситет «Днiпровська полiтехнiка»

Аспірант кафедри системного аналізу та управління

Посилання

  1. Koriashkina, L. S., & Lubenets, D. Y. (2023). Mathematical models of multiplex partitioning and multiple coverage of sets for the location-allocation problems. Information Technology: Computer Science, Software Engineering and Cyber Security, 4, 20–31. https://doi.org/10.32782/IT/2023-4-3 [in Ukranian].
  2. Koryashkina, L. S., & Cherevatenko, A. P. (2015). Continuous linear problems of optimal multiplex partitioning of sets with constraints. Bulletin of the V. N. Karazin Kharkiv National University, Series "Math. modeling. Information technologies. Automated control systems", 28, 77–91 [in Russian].
  3. Koriashkina, L. S., Cherevatenko, A. P., & Koriashkina, E. O. (2017). Integration of GIS technologies and methods of solving continuous problems of optimal multiplex-partitioning of sets. System research and information technologies, (4), 97–108. https://doi.org/10.20535/SRIT.2308-8893.2017.4.08 [in Russian].
  4. Rodríguez-Espíndola, O., Ahmadi, H., Gastélum-Chavira, D., Ahumada-Valenzuela, O., Chowdhury, S., Dey, P. K., & Albores, P. (2023). Humanitarian logistics optimization models: An investigation of decision-maker involvement and directions to promote implementation. Socio-Economic Planning Sciences, 89, Article 101669. https://doi.org/10.1016/j.seps.2023.101669
  5. Pooja Kumar, R., Viriyasitavat, W., Yadav, K., & Dhiman, G. (2023). Analysis of Clustering Algorithms for Facility Location Allocation Problems. In: Reddy, A. B., Nagini, S., Balas, V. E., & Raju, K. S. (eds). Proceedings of Third International Conference on Advances in Computer Engineering and Communication Systems. Lecture Notes in Networks and Systems. (Vol. 612). Springer: Singapore. https://doi.org/10.1007/978-981-19-9228-5_51
  6. Drezner, Z., & Eiselt, H. A. (2024). Competitive location models: A review. European Journal of Operational Research, 316(1), 5–18. https://doi.org/10.1016/j.ejor.2023.10.030
  7. Drezner, Z. (2022). Continuous Facility Location Problems. The Palgrave Handbook of Operations Research. Palgrave Macmillan: Cham. https://doi.org/10.1007/978-3-030-96935-6_9
  8. Han, J., Zhang, J., Zeng, B., & Mao, M. (2021). Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition. Omega, 105, 102498. https://doi.org/10.1016/j.omega.2021.102498
  9. Sergeiev, O. S., & Us, S. A. (2024). Exploring Two Solution Methods for the Two-Stage Location-Activation Problem. Scientific Bulletin of Uzhhorod University. Series of Mathematics and Informatics, 45(2), 249–258. https://doi.org/10.24144/2616-7700.2024.45(2).249-258 [in Ukranian].
  10. Koriashkina, L. S., & Lubenets, D. Y. (2024). Systems analysis and mathematical modeling of partially two-stage processes of material flow distribution. System technologies, 1, 86–99. https://doi.org/10.34185/1562-9945-1-150-2024-08 [in Ukranian].
  11. Dziuba, S. V., Koriashkina, L. S., Stanina, O. D., & Lubenets, D. Y. (2023). Mathematical models of optimization problems of partially two-stage population evacuation with territory segmentation. Information Technology: Computer Science, Software Engineering and Cyber Security, 3, 13–21. https://doi.org/10.32782/IT/2023-3-2 [in Ukranian].
  12. Yang, Y., Yin, Y., Wang, D., Ignatius, J., & Dhamotharan, L. (2023). Distributionally robust multi-period location-allocation with multiple resources and capacity levels in humanitarian logistics. European Journal of Operational Research, 305(3), 1042–1062. https://doi.org/10.1016/j.ejor.2022.06.047
  13. Moslemi, S., & Pasandideh, S. H. R. (2021). A location-allocation model for quality-based blood supply chain under IER uncertainty. RAIRO — Operations Research, 55, 967–998. https://doi.org/10.1051/ro/2020035
  14. Zemlianyi, O., & Baibuz, O. (2024). Vectorization of calculations for code optimization in the Python programming language. Challenges and Issues of Modern Science, 3, 145–149. https://cims.fti.dp.ua/j/article/view/215 [in Ukranian].
  15. Arora, I. (2024). Improving Performance of Data Science Applications in Python. Indian Journal of Science and Technology, 17(24), 2499–2507. https://doi.org/10.17485/IJST/v17i24.914

##submission.downloads##

Опубліковано

2025-06-03

Як цитувати

Лубенець, Д. Є. (2025). Оптимізація обчислень в алгоритмах мультиплексного розбиття континуальних множин. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 46(1), 195–208. https://doi.org/10.24144/2616-7700.2025.46(1).195-208

Номер

Том 46 № 1 (2025)

Розділ

Iнформатика, комп’ютернi науки та прикладна математика

Ліцензія

Авторське право (c) 2025 Д. Є. Лубенець

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.