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

On an iterative method for solving linear programming problems on cluster computing systems

The paper was recommended by the Programm Committee of th International Conference "Russian Supercomputing Days"

Authors

  • L.B. Sokolinsky
  • Irina Sokolinskaya

Keywords:

linear programming
large-scale problems
apex-method
predictor–corrector framework
iterative method
parallel algorithm
cluster computing system

Abstract

The paper is devoted to a new method for solving large-scale linear programming (LP) problems. This method is called the apex-method. The apex-method uses the predictor–corrector framework. Thepredictor step calculates a point belonging to the feasible region of the LP problem. The corrector step calculates a sequence of points converging to the exact solution of the LP problem. The paper gives a formal description of the apex-method and provides information about its parallel implementation in C++ language using the MPI library. The results of large-scale computational experiments on a cluster computing system to study the scalability of the apex method are discussed.

New computational technologies

Downloads

Published

2020-09-27

Issue

Vol. 21 (2020): Issue 3.

Section

Parallel software tools and technologies

Author Biographies

L.B. Sokolinsky

South Ural State University (national research university)
• Professor, Vice Rector

Irina Sokolinskaya

South Ural State University (national research university)
• Associate Professor

References

  1. H. V. Jagadish, J. Gehrke, A. Labrinidis, et al., “Big Data and Its Technical Challenges,” Commun. ACM 57 (7), 86-94 (2014).
  2. T. Hartung, “Making Big Sense from Big Data,” Frontiers in Big Data 1 (2018).
    doi 10.3389/fdata.2018.00005
  3. I. M. Sokolinskaya and L. B. Sokolinsky, “On the Solution of Linear Programming Problem in the Era of Big Data,” in Proc. Int. Conf. on Parallel Computational Technologies, Kazan, Russia, April 3-7, 2017 (South Ural State Univ., Chelyabinsk, 2017), pp. 471-484.
  4. W. Chung, “Applying Large-Scale Linear Programming in Business Analytics,” in Proc. IEEE Int. Conf. on Industrial Engineering and Engineering Management Singapore, December 6-9, 2015 (IEEE Press, New York, 2016), pp. 1860-1864.
  5. 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).
  6. M. S. Sodhi, “LP Modeling for Asset-Liability Management: A Survey of Choices and Simplifications,” Oper. Res. 53 (2), 181-196 (2005).
  7. J. Brogaard, T. Hendershott, and R. Riordan, “High-Frequency Trading and Price Discovery,” Rev. Financ. Stud. 27 (8), 2267-2306 (2014).
  8. R. E. Bixby, “Solving Real-World Linear Programs: A Decade and More of Progress,” Oper. Res. 50 (1), 3-15 (2002).
  9. J. Dongarra, S. Gottlieb, and W. T. C. Kramer, “Race to Exascale,” Comput. Sci. Eng. 21 (1), 4-5 (2019).
  10. G. B. Dantzig, Linear Programming and Extensions (Princeton Univ. Press, Princeton, 1998).
  11. V. Klee and G. J. Minty, “How Good is the Simplex Algorithm?,” in Inequalities III (Academic, New York, 1972), Vol. 3, pp. 159-175.
  12. R. G. Jeroslow, “The Simplex Algorithm with the Pivot Rule of Maximizing Criterion Improvement,” Discrete Math. 4 (4), pp. 367-377 (1973).
  13. N. Zadeh, “A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms,” in Mathematical Programming (Springer, Berlin, 1973), Vol. 5, pp. 255-266.
  14. R. H. Bartels, J. Stoer, and Ch. Zenger, “A Realization of the Simplex Method Based on Triangular Decompositions,” in Handbook for Automatic Computation. Vol. II: Linear Algebra (Springer, Berlin, 1971), pp. 152-190.
  15. P. Tolla, “A Survey of Some Linear Programming Methods,” in Concepts of Combinatorial Optimization (Wiley, Hoboken, 2014), pp. 157-188.
  16. B. Mamalis and G. Pantziou, “Advances in the Parallelization of the Simplex Method,” in Lecture Notes in Computer Science (Springer, Cham, 2015), Vol. 9295, pp. 281-307.
  17. M. Lubin, J. A. J. Hall, C. G. Petra, and M. Anitescu, “Parallel Distributed-Memory Simplex for Large-Scale Stochastic LP Problems,” Comput. Optim. Appl. 55 (3), 571-596 (2013).
  18. L. G. Khachiyan, “A Polynomial Algorithm in Linear Programming,” Dokl. Akad. Nauk. SSSR 244 (5), 1093-1096 (1979) [Sov. Math. Dokl. 20, 191-194 (1979)].
  19. N. Z. Shor, “Cut-off Method with Space Extension in Convex Programming Problems,” Kibernetika, No. 1, 94-95 (1977) [Cybernetics 13 (1), 94-95 (1977)].
  20. D. B. Yudin and A. S. Nemirovskii, “Informational Complexity and Effective Methods for the Solution of Convex Extremal Problems,” Ekonomika Mat. Metody 12 (2), 357-369 (1976).
  21. N. Karmarkar, “A New Polynomial-Time Algorithm for Linear Programming,” Combinatorica 4 (4), 373-395 (1984).
  22. S. Fathi-Hafshejani, H. Mansouri, M. R. Peyghami, and S. Chen, “Primal-Dual Interior-Point Method for Linear Optimization Based on a Kernel Function with Trigonometric Growth Term,” Optimization 67 (10), 1605-1630 (2018).
  23. S. Asadi and H. Mansouri, “A Mehrotra Type Predictor-Corrector Interior-Point Algorithm for Linear Programming,” Numer. Algebra Control Optim. 9 (2), 147-156 (2019).
  24. Y. Yuan, “Implementation Tricks of Interior-Point Methods for Large-Scale Linear Programs,” Proc. SPIE 8285, Graphic and Image Processing (2011).
    doi 10.1117/12.913019
  25. B. Kheirfam and M. Haghighi, “A Full-Newton Step Infeasible Interior-Point Method for Linear Optimization Based on a Trigonometric Kernel Function,” Optimization 65 (4), 841-857 (2016).
  26. Y. Xu, L. Zhang, and J. Zhang, “A Full-Modified-Newton Step Infeasible Interior-Point Algorithm for Linear Optimization,” J. Ind. Manag. Optim. 12 (1), 103-116 (2016).
  27. C. Roos, T. Terlaky, and J.-P. Vial, Interior Point Methods for Linear Optimization (Springer, New York, 2005).
  28. I. Sokolinskaya, “Parallel Method of Pseudoprojection for Linear Inequalities,” in Parallel Computational Technologies (Springer, Cham, 2018), Vol. 910, pp. 216-231.
  29. H. Hafsteinsson, R. Levkovitz, and G. Mitra, “Solving Large Scale Linear Programming Problems Using an Interior Point Method on a Massively Parallel SIMD Computer,” Parallel Algorithms Appl. 4 (3-4), 301-316 (1994).
  30. G. Karypis, A. Gupta, V. Kumar, “A Parallel Formulation of Interior Point Algorithms,” in Proc. 1994 ACM/IEEE Conf. on High Performance Computing, Networking, Storage, and Analysis, Washington, DC, USA, November 14-18, 1994 (IEEE Press, Los Alamitos, 1994), pp. 204-213.
  31. A. V. Ershova, I. M. Sokolinskaya, “About Convergence of Scalable Algorithm of Construction Pseudoprojection on Convex Closed Set,” Vestn. South Ural State Univ. Ser. Mat. Model. Program., No. 37, 12-21 (2011).
  32. I. M. Sokolinskaya and L. B. Sokolinsky, “Revised Pursuit Algorithm for Solving Unstable Linear Programming Problems on Modern Computing Clusters with Manycore Accelerators,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 26-27, 2016 (Mosk. Gos. Univ., Moscow, 2016), pp. 294-306.
  33. I. M. Sokolinskaya and L. B. Sokolinsky, “Scalability Evaluation of a Modified Cimmino Algorithm for Linear Inequalities,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 24-25, 2018 (Mosk. Gos. Univ., Moscow, 2018), pp. 673-683.
  34. I. I. Eremin, Fejer Methods for Problems of Convex and Linear Optimization (South Ural State Univ., Chelyabinsk, 2009) [in Russian].
  35. I. M. Sokolinskaya and L. B. Sokolinsky, “A Scalable Algorithm for Solving Non-Stationary Linear Programming Problems,” Vychisl. Metody Programm. 19, 540-550 (2018).
  36. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes: The Art of Scientific Computing (Cambridge Univ. Press, New York, 2007).
  37. Y. Censor, T. Elfving, G. T. Herman, and T. Nikazad, “On Diagonally Relaxed Orthogonal Projection Methods,” SIAM J. Sci. Comput. 30 (1), 473-504 (2008).
  38. L. B. Sokolinsky and I. M. Sokolinskaya, “Parallel Algorithm for Solving Non-Stationary Systems of Linear Inequalities,” in Proc. 14th Int. Conf. on Parallel Computational Technologies, Perm, Russia, March 31-April 2, 2020 (South Ural State Univ., Chelyabinsk, 2020), pp. 275-286.
  39. N. A. Ezhova and L. B. Sokolinsky, “BSF: A model of Parallel Computation for Multiprocessor Systems with Distributed Memory,” in Proc. Int. Conf. on Parallel Computational Technologies, Rostov-on-Don, Russia, April 2-6, 2018 (South Ural State Univ., Chelyabinsk, 2018), pp. 253-265.
  40. N. A. Ezhova and L. B. Sokolinsky, “Parallel Сomputational Model for Multiprocessor Systems with Distributed Memory,” Vestn. South Ural State Univ. Ser. Vychisl. Mat. Inf. 7 (2), 32-49 (2018).
  41. L. B. Sokolinsky, “BSF-skeleton,” (2019)
    https://github.com/leonid-sokolinsky/BSF-skeleton . Cited August 27, 2020.
  42. N. A. Ezhova and L. B. Sokolinsky, “BSF-MR Parallel Computation Model,” Sistemy Upravl. Inf. Tekhnol., No. 3, 15-21 (2019).
  43. P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computing Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. 1576, 561-573 (2016).
  44. D. M. Gay, “Netlib-Lp,”
    http://www.netlib.org/lp/. Cited August 27, 2020.
  45. T. Koch, “The Final NETLIB-LP Results,” Oper. Res. Lett. 32 (2), 138-142 (2004).

License

Copyright (c) 2020 Numerical methods and programming

Creative Commons License

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