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

Finding optimal vertex on polytope of feasible solutions to linear programming problem

Authors

  • Alexander E. Zhulev
  • Leonid B. Sokolinsky

Keywords:

linear programming
projection method
parallel implementation
MPI
cluster computing system
scalability analysis
AlEM algorithm

Abstract

A new scalable AlEM algorithm for linear programming on cluster computing systems is presented. Unlike the classical simplex method, the AlEM algorithm, at each step, examines all edges coming from the current vertex of the polytope of feasible solutions, which guarantees the construction of a suboptimal path and completely prevents circling in degenerate problems. A formalized description of the algorithm and its parallel implementation using the MPI library is given.The scalability of the parallel version of the algorithm on real and synthetic linear programming problems has been experimentally investigated. The results of computational experiments confirm the high parallel efficiency of the AlEM algorithm, which remains at least 46% when using up to 200 processor nodes. It is shown that the AlEM algorithm is a possible alternative to existing linear programming methods for high-performance computing.


Downloads

Published

2026-01-21

Issue

Vol. 27 (2026): Issue 1.

Section

Methods and algorithms of computational mathematics and their applications

Authors

Alexander E. Zhulev

South Ural State University (National Research University)

• PhD Student

Leonid B. Sokolinsky

South Ural State University (National Research University)

• Professor, Head of Department

References

  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

License

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

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.