AlEM: новый параллельный алгоритм линейного программирования для кластерных вычислительных систем

Александр Эдуардович Жулев,Леонид Борисович Соколинский

ПРЕПРИНТ

Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.

AlEM: новый параллельный алгоритм линейного программирования для кластерных вычислительных систем

А. Э. Жулев,

Л. Б. Соколинский

2025-05-06

https://doi.org/10.24108/preprints-3113529

Работа посвящена новому масштабируемому проекционному алгоритму AlEM (Along Edges Movement) для линейного программирования на кластерных вычислительных системах. Алгоритм начинает свою работу в произвольной вершине многогранника допустимых решений и строит оптимальный путь по ребрам до точки оптимума. Представлено формализованное описание алгоритма. Описана его параллельная реализация. Исследована масштабируемость параллельной реализации на кластерной вычислительной системе. Приведены результаты вычислительных экспериментов, подтверждающие высокую параллельную эффективность алгоритма AlEM.

Ссылка для цитирования:

Жулев А. Э., Соколинский Л. Б. 2025. AlEM: новый параллельный алгоритм линейного программирования для кластерных вычислительных систем. PREPRINTS.RU. https://doi.org/10.24108/preprints-3113529

Список литературы

1. Xu Y. Solving Large Scale Optimization Problems in the Transportation Industry and Beyond Through Column Generation // Optimization in Large Scale Problems. Springer Optimization and Its Applications, vol 152. Springer, 2019. P. 269-292. DOI: 10.1007/978-3-030-28565-4_23/COVER.

2. Chung W. Applying large-scale linear programming in business analytics // 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2015. P. 1860-1864. DOI: 10.1109/IEEM.2015.7385970.

3. Gondzio J., Gruca J.A., Hall J.A.J., et al. Solving large-scale optimization problems related to Bell's Theorem // Journal of Computational and Applied Mathematics. 2014. Vol. 263. P. 392-404. DOI: 10.1016/j.cam.2013.12.003.

4. Dantzig G.B. Linear programming and extensions. Princeton, N.J.: Princeton university press, 1998. 656 p.

5. Зоркальцев В.И., Мокрый И.В. Алгоритмы внутренних точек в линейной оптимизации // Сибирский журнал индустриальной математики. 2018. Т. 21, 1 (73). C. 11–20. DOI: 10.17377/sibjim.2018.21.102.

6. Kaczmarz S. Angenherte Ausung von Systemen linearer Gleichungen // Bulletin International de l'Acadmie Polonaise des Sciences et des Lettres. Classe des Sciences Mathmatiques et Naturelles. Srie A, Sciences Mathmatiques. 1937. Vol. 35. P. 355-357.

7. Cimmino G. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari // La Ricerca Scientica, XVI, Series II, Anno IX, 1. 1938. P. 326-333.

8. Agmon S. The relaxation method for linear inequalities // Canadian Journal of Mathematics. 1954. Vol. 6. P. 382-392. DOI: 10.4153/CJM-1954-037-2.

9. Censor Y., Chen W., Combettes P.L., et al. On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints // Computational Optimization and Applications. 2011. Vol. 51, no. 3. P. 1065_1088. DOI: 10.1007/S10589-011-9401-7.

10. Ерёмин И.И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями // Журнал вычислительной математики и математической физики. 1969. Т. 9, № 5. C. 1153–1160.

11. Васин В.В., Ерёмин И.И. Операторы и итерационные процессы фейеровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. 211 с.

12. Ерёмин И.И., Попов Л.Д. Фейеровские процессы в теории и практике: обзор последних результатов // Известия вузов. Математика. 2009. № 1. C. 44–65. URL: https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ivm&paperid=1253.

13. Nurminski E.A. Single-projection procedure for linear optimization // Journal of Global Optimization. 2016. Vol. 66, no. 1. P. 95-110. DOI: 10.1007/S10898-015-0337-9.

14. Censor Y. Can linear superiorization be useful for linear optimization problems? // Inverse Problems. 2017. Vol. 33, no. 4. P. 044006. DOI: 10.1088/1361-6420/33/4/044006.

15. Соколинский Л.Б., Соколинская И.М. О новой версии апекс-метода для решения задач линейного программирования // ВестникЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 2. C. 5–46. DOI: 10.14529/cmse230201.

16. Deutsch F., Hundal H. The rate of convergence for the cyclic projections algorithm I: Angles between convex sets // Journal of Approximation Theory. 2006. Vol. 142, no. 1. P. 36-55. DOI: 10.1016/J.JAT.2006.02.005.

17. Aharoni R., Censor Y. Block-iterative projection methods for parallel computation of solutions to convex feasibility problems // Linear Algebra and its Applications. 1989. Vol. 120. P. 165-175. DOI: 10.1016/0024-3795(89)90375-3.

18. Соколинский Л.Б., Ольховский Н.А., Соколинская И.М. Численная реализация метода поверхностного движения для решения задач линейного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2024. Т. 13, № 3. C. 5–31. DOI: 10.14529/cmse240301.

19. Ольховский Н.А., Соколинский Л.Б. О новом методе линейного программирования // Вычислительные методы и программирование. 2023. Т. 24, № 4. C. 408–429. DOI: 10. 26089/NumMet.v24r428.

20. Мальцев А.И. Основы линейной алгебры. Москва: Наука. Главная редакция физикоматематической литературы, 1970. 402 с.

21. Chase P.J. Algorithm 382: combinations of M out of N objects [G6] // Communications of the ACM. 1970. Vol. 13, no. 6. P. 368. DOI: 10.1145/362384.362502.

22. Gould N.I. How good are projection methods for convex feasibility problems? // Computational Optimization and Applications. 2008. Vol. 40, no. 1. P. 1-12. DOI: 10.1007/S10589-007-9073-5.

23. Boisvert R.F., Pozo R., Remington K.A. The Matrix Market Exchange Formats: Initial Design: tech. rep. / NISTIR 5935. National Institute of Standards; Technology. Gaithersburg, MD, 1996. P. 14. URL: https://nvlpubs.nist.gov/nistpubs/Legacy/IR/nistir5935.pdf.

24. Соколинский Л.Б., Соколинская И.М. О генерации случайных задач линейного программирования на кластерных вычислительных системах // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2021. Т. 10, № 2. C. 38–52. DOI: 10.14529/cmse210103.

25. Dolganina N., Ivanova E., Bilenko R., Rekachinsky A. HPC Resources of South Ural State University // Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science, vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. City: Cham: Springer, 2022. P. 43-55. DOI: 10.1007/978-3-031-11623-0_4.

ПРЕПРИНТ

ИНФОРМАЦИЯ