Исследование масштабируемости параллельной реализации алгоритма AlFaMove для линейного программирования на кластерной вычислительной системе

Николай Александрович Ольховский,Леонид Борисович Соколинский

ПРЕПРИНТ

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

Исследование масштабируемости параллельной реализации алгоритма AlFaMove для линейного программирования на кластерной вычислительной системе

Н. А. Ольховский,

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

2024-05-29

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

Работа посвящена параллельной реализации нового алгоритма линейного программирования, получившего название AlFaMove. Алгоритм строит на поверхности допустимого многогранника оптимальный целевой путь от произвольной граничной точки до точки, являющейся решением задачи линейного программирования. Оптимальность пути заключается в том, что при поиске точки максимума целевой функции выбирается направление движения по грани многогранника, соответствующее максимальному увеличению значения целевой функции. Для вычисления направления движения используется итерационный алгоритм проекционного типа. Выполнена параллельная реализация алгоритма AlFaMove. Приведены результаты вычислительных экспериментов на кластерной вычислительной системе, демонстрирующие высокую масштабируемость предложенной реализации.

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

Ольховский Н. А., Соколинский Л. Б. 2024. Исследование масштабируемости параллельной реализации алгоритма AlFaMove для линейного программирования на кластерной вычислительной системе. PREPRINTS.RU. https://doi.org/10.24108/preprints-3113052

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

1. Optimization in Large Scale Problems: Industry 4.0 and Society 5.0 Applications / ed. by M. Fathi, M. Khaki_rooz, P.M. Pardalos. Cham, Switzerland: Springer, 2019. XI, 340 p. DOI: 10.1007/978-3-030-28565-4.

2. Kopanos G.M., Puigjaner L. Solving Large-Scale Production Scheduling and Planning in the Process Industries. Cham, Switzerland: Springer, 2019. 1_291 p. DOI: 10.1007/978-3-030-01183-3.

3. Schlenkrich M., Parragh S.N. Solving large scale industrial production scheduling problems with complex constraints: an overview of the state-of-the-art // 4th International Conference on Industry 4.0 and Smart Manufacturing. Procedia Computer Science. Vol. 217 / ed. by F. Longo, M. A_enzeller, A. Padovano, W. Shen. Elsevier, 2023. P. 1028-1037. DOI: 10.1016/J.PROCS.2022.12.301.

4. Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии (ПаВТ’2017). Короткие статьи и описания плакатов. Челябинск: Издательский центрЮУрГУ, 2017. C. 471-484. URL: http://omega.sp.susu.ru/pavt2017/short/014.pdf.

5. Branke J. Optimization in Dynamic Environments // Evolutionary Optimization in Dynamic Environments. Genetic Algorithms and Evolutionary Computation, vol. 3. Boston, MA: Springer, 2002. P. 13-29. DOI: 10.1007/978-1-4615-0911-0_2.

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

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

8. Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method // Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295 / ed. by C. Zaroliagis, G. Pantziou, S. Kontogiannis. City: Cham: Springer, 2015. P. 281-307. DOI: 10.1007/978-3-319-24024-4_17.

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

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

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

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

13. 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.

14. Sokolinsky L.B. BSF: A parallel computation model for scalability estimation of iterative numerical algorithms on cluster computing systems // Journal of Parallel and Distributed Computing. 2021. Vol. 149. P. 193-206. DOI: 10.1016/j.jpdc.2020.12.009.

15. Sokolinsky L.B. BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems // MethodsX. 2021. Vol. 8. Article number 101437. DOI: 10.1016/j.mex.2021.101437.

16. 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.

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

18. Соколинский Л.Б., Соколинская И.М. О валидации решений задач линейного программирования на кластерных вычислительных системах // Вычислительные методы и программирование. 2021. Т. 22, № 4. C. 252-261. DOI: 10.26089/NUMMET.V22R416.

19. Gay D.M. Electronic mail distribution of linear programming test problems // Mathematical Programming Society COAL Bulletin. 1985. Vol. 13. P. 10-12.

ПРЕПРИНТ

ИНФОРМАЦИЯ