DOI: https://doi.org/10.26089/NumMet.v27r101

О поиске оптимальной вершины на многограннике допустимых решений задачи линейного программирования

Авторы

  • А. Э. Жулев
  • Л. Б. Соколинский

Ключевые слова:

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

Аннотация

Представлен новый масштабируемый алгоритм AlEM для решения задач линейного программирования на кластерных вычислительных системах. В отличие от классического симплекс-метода, алгоритм AlEM на каждом шаге исследует все исходящие из текущей вершины ребра многогранника допустимых решений, что гарантирует построение субоптимального пути и полностью исключает возможность зацикливания на вырожденных задачах. Приведено формализованное описание алгоритма и его параллельной реализации с использованием библиотеки MPI. Экспериментально исследована масштабируемость параллельной версии алгоритма на реальных и модельных задачах линейного программирования. Результаты вычислительных экспериментов подтверждают высокую параллельную эффективность алгоритма AlEM, которая сохраняется на уровне не менее 46% при использовании до 200 процессорных узлов. Показано, что алгоритм AlEM является возможной альтернативой существующим методам линейного программирования для высокопроизводительных вычислений.


Загрузки

Опубликован

2026-01-21

Выпуск

Том 27 (2026): Выпуск 1.

Раздел

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

Авторы

А. Э. Жулев

Южно-Уральский государственный университет

• аспирант

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

Южно-Уральский государственный университет

• профессор, заведующий кафедрой

Библиографические ссылки

  1. Y. Xu, “Solving Large Scale Optimization Problems in the Transportation Industry and Beyond Through Column Generation,” in Optimization in Large Scale Problems. Springer Optimization and Its Applications, Vol. 152(Springer, Cham, 2019), pp. 269–292.
    doi 10.1007/978-3-030-28565-4_23
  2. W. Chung, “Applying Large-Scale Linear Programming in Business Analytics,” in 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, December 06–09, 2015(IEEE Press, 2015), pp. 1860–1864.
    doi 10.1109/IEEM.2015.7385970
  3. J. Gondzio, J. A. Gruca, J. A. J. Hall, et al., “Solving Large-Scale Optimization Problems Related to Bell’s Theorem,” J. Comput. Appl. Math. 263, 392–404 (2014).
    doi 10.1016/j.cam.2013.12.003
  4. K. G. Murty, “Linear Equations, Inequalities, Linear Programs, and a New Efficient Algorithm,” in Tutorials in Operations Research: Models, Methods, and Applications for Innovative Decision Making(INFORMS, Catonsville, 2006), pp. 1–36.
    doi 10.1287/educ.1063.0024
  5. G. B. Dantzig, Linear Programming and Extensions(Princeton University Press, Princeton, N.J., 1998).
  6. P. Tolla, “A Survey of Some Linear Programming Methods,” in Concepts of Combinatorial Optimization. 2-nd ed.(Wiley, Hoboken, 2014), pp. 157–188.
    doi 10.1002/9781119005216.ch7
  7. A. Schrijver, Theory of Linear and Integer Programming(Wiley and Sons, New York, 1998).
  8. T. C. T. Kotiah and D. I. Steinberg, “Letter to the Editor – On the Possibility of Cycling with the Simplex Method,” Oper. Res. 26 (2), 374–376 (1978).
    doi 10.1287/OPRE.26.2.374
  9. S. I. Gass and S. Vinjamuri, “Cycling in Linear Programming Problems,” Comput. Oper. Res. 31 (2), 303–311 (2004).
    doi 10.1016/S0305-0548(02)00226-5
  10. J. A. J. Hall and K. I. M. McKinnon, “The Simplest Examples where the Simplex Method Cycles and Conditions where EXPAND Fails to Prevent Cycling,” Math. Program. Ser. B 100 (1), 133–150 (2004).
    doi 10.1007/s10107-003-0488-1
  11. I. Maros, “Large Scale LP Problems,” in Computational Techniques of the Simplex Method(International Series in Operations Research and Management Science, Vol. 61) (Springer, Boston, 2003), pp. 49–56.
    doi 10.1007/978-1-4615-0257-9_3
  12. M. Schlenkrich and S. N. Parragh, “Solving Large Scale Industrial Production Scheduling Problems with Complex Constraints: An Overview of the State-of-the-Art,” in 4th International Conference on Industry 4.0 and Smart Manufacturing(Procedia Computer Science, Vol. 217. Elsevier, 2023), pp. 1028–1037.
  13. B. Mamalis and G. Pantziou, “Advances in the Parallelization of the Simplex Method,” in Algorithms, Probability, Networks, and Games(Lecture Notes in Computer Science, Vol. 9295) (Springer, Cham, 2015), pp. 281–307.
    doi 10.1007/978-3-319-24024-4_17
  14. V. Klee and G. J. Minty, “How Good Is the Simplex Algorithm?’’ in Inequalities – III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1–9, 1969(Academic Press, New York, 1972), pp. 159–175.
  15. K. G. Murty, Computational and Algorithmic Linear Algebra and n-Dimensional Geometry(World Scientific Publishing Company, Singapore, 2014).
    doi 10.1142/8261
  16. G. Strang, Linear Algebra and Its Applications(Academic Press, New York, 1980).
  17. L. Khachiyan, “Fourier–Motzkin Elimination Method,” in Encyclopedia of Optimization(Springer, Boston, 2008), pp. 1074–1077.
    doi 10.1007/978-0-387-74759-0_187
  18. A. E. Zhulev, L. B. Sokolinsky, and I. M. Sokolinskaya, “On Calculating a Vertex of Feasible Solutions Polytope of Linear Constraints System,” Bull. South Ural State Univ. Ser. Comput. Math. Softw. Eng. 14 (3), 5–27 (2025).
    doi 10.14529/cmse250301
  19. P. J. Chase, “Algorithm 382: Combinations of M out of N Objects [G6],” Communications of the ACM 13 (6), 368–368 (1970).
    doi 10.1145/362384.362502
  20. W. Gropp, “MPI 3 and Beyond: Why MPI Is Successful and What Challenges It Faces,” in Recent Advances in the Message Passing Interface. EuroMPI 2012. Lecture Notes in Computer Science(Springer, Berlin, 2012), Vol. 7490, pp. 1–9.
  21. D. M. Gay, “Electronic Mail Distribution of Linear Programming Test Problems,” Mathematical Programming Society COAL Newsletter 13, 10–12 (1985).
  22. T. Koch, “The Final NETLIB-LP Results,” Operations Research Letters 32 (2), 138–142 (2004).
    doi 10.1016/S0167-6377(03)00094-4
  23. A. E. Zhulev and L. B. Sokolinsky, “AlEM: A New Parallel Linear Programming Algorithm for Cluster Computing Systems,” in Russian Supercomputing Days: Proceedings of the International Conference. Moscow, Russia, September 29–30, 2025(MAKS Press, Moscow, 2025), pp. 4–24.
    doi 10.29003/m4750.978-5-317-07451-7 [in Russian].
  24. B. A. Murtagh, Advanced Linear Programming: Computation and Practice(McGraw-Hill, New York, 1981).
  25. R. F. Boisvert, R. Pozo, and K. A. Remington, The Matrix Market Exchange Formats: Initial Design: tech. rep. / NISTIR 5935(NIST, Gaithersburg, MD, 1996).
    https://nvlpubs.nist.gov/nistpubs/Legacy/IR/nistir5935.pdf Cited December 29, 2025.
  26. N. Dolganina, E. Ivanova, R. Bilenko, and A. Rekachinsky, “HPC Resources of South Ural State University,” in Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science(Cham: Springer, 2022), Vol. 1618, pp. 43–55.
    doi 10.1007/978-3-031-11623-0_4

Лицензия

Copyright (c) 2026 А. Э. Жулев, Леонид Борисович Соколинский

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.