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

DOI:

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

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.

Author Biographies

L.B. Sokolinsky

Irina Sokolinskaya

References

  1. Jagadish H.V., Gehrke J., Labrinidis A., et al. Big data and its technical challenges // Communications of the ACM. 2014. 57, N 7. 86–94.
  2. Hartung T. Making big sense from big data // Frontiers in Big Data. 2018. 1. doi 10.3389/fdata.2018.00005.
  3. Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии — XI международная конференция, ПаВТ’2017, г. Казань, 3–7 апреля 2017 г. Челябинск: Издательский центр ЮУрГУ, 2017. 471–484.
  4. Chung W. Applying large-scale linear programming in business analytics // Proc. 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). New York: IEEE Press, 2016. 1860–1864.
  5. 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. 263. 392-404.
  6. Sodhi M.S. LP modeling for asset-liability management: a survey of choices and simplifications // Operations Research. 2005. 53, N 2. 181–196.
  7. Brogaard J., Hendershott T., Riordan R. High-frequency trading and price discovery // Review of Financial Studies. 2014. 27, N 8. 2267–2306.
  8. Bixby R.E. Solving real-world linear programs: a decade and more of progress // Operations research. 2002. 50, N 1. 3–15.
  9. Dongarra J., Gottlieb S., Kramer W.T. C. Race to exascale // Computing in Science & Engineering. 2019. 21, N 1. 4–5.
  10. Dantzig G.B. Linear programming and extensions. Princeton: Princeton Univ. Press, 1998.
  11. Klee V., Minty G.J. How good is the simplex algorithm? // Inequalities–III. Vol. 3. New York: Academic Press, 1972. 159–175.
  12. Jeroslow R.G. The simplex algorithm with the pivot rule of maximizing criterion improvement // Discrete Mathematics. 1973. 4, N 4. 367–377.
  13. Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms // Mathematical Programming. 1973. 5, N 1. 255–266.
  14. Bartels R.H., Stoer J., Zenger Ch. A realization of the simplex method based on triangular decompositions // Handbook for Automatic Computation. Vol. II: Linear Algebra. Berlin: Springer, 1971. 152–190.
  15. Tolla P. A survey of some linear programming methods // Concepts of Combinatorial Optimization. Hoboken: Wiley, 2014. 157–188.
  16. Mamalis B., Pantziou G. Advances in the parallelization of the simplex method // Lecture Notes in Computer Science. Vol. 9295. Cham: Springer, 2015. 281–307.
  17. Lubin M., Hall J.A. J., Petra C.G., Anitescu M. Parallel distributed-memory simplex for large-scale stochastic LP problems // Computational Optimization and Applications. 2013. 55, N 3. 571–596.
  18. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР. 1979. 244, № 5. 1093–1096.
  19. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования // Кибернетика. 1977. 13, № 1. 94–95.
  20. Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и математические методы. 1976. 12, № 2. 357–369.
  21. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373–395.
  22. Fathi-Hafshejani S., Mansouri H., Peyghami M.R., Chen S. Primal-dual interior-point method for linear optimization based on a kernel function with trigonometric growth term // Optimization. 2018. 67, N 10. 1605–1630.
  23. Asadi S., Mansouri H. A Mehrotra type predictor–corrector interior-point algorithm for linear programming // Numerical Algebra, Control and Optimization. 2019. 9, N 2. 147–156.
  24. Yuan Y. 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. Kheirfam B., Haghighi M. A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function // Optimization. 2016. 65, N 4. 841–857.
  26. Xu Y., Zhang L., Zhang J. A full-modified-Newton step infeasible interior-point algorithm for linear optimization // Journal of Industrial and Management Optimization. 2016. 12, N 1. 103–116.
  27. Roos C., Terlaky T., Vial J.-P. Interior point methods for linear optimization. New York: Springer, 2005.
  28. Sokolinskaya I. Parallel method of pseudoprojection for linear inequalities // Parallel Computational Technologies. Vol. 910. Cham: Springer, 2018. 216–231.
  29. Hafsteinsson H., Levkovitz R., Mitra G. Solving large scale linear programming problems using an interior point method on a massively parallel SIMD computer // Parallel Algorithms and Applications. 1994. 4, N 3–4. 301–316.
  30. Karypis G., Gupta A., Kumar V. A parallel formulation of interior point algorithms // Proc. 1994 ACM/IEEE Conference on High Performance Computing, Networking, Storage, and Analysis. Los Alamitos: IEEE Press, 1994. 204–213.
  31. Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. 2011. № 37. 12–21.
  32. Соколинская И.М., Соколинский Л.Б. Модифицированный следящий алгоритм для решения нестационарных задач линейного программирования на кластерных вычислительных системах с многоядерными ускорителями // Суперкомпьютерные дни в России: Труды международной конференции (26–27 сентября 2016 г., г. Москва). Москва: Изд-во МГУ, 2016. 294–306.
  33. Соколинская И.М., Соколинский Л.Б. Исследование масштабируемости модифицированного алгоритма Чиммино для линейных неравенств // Суперкомпьютерные дни в России: Труды международной конференции (24–25 сентября 2018 г., г. Москва). Москва: Изд-во МГУ, 2018. 673–683.
  34. Ерёмин И.И. Фейеровские методы для задач выпуклой и линейной оптимизации. Челябинск: Издательский центр ЮУрГУ, 2009.
  35. Соколинская И.М., Соколинский Л.Б. Масштабируемый алгоритм для решения нестационарных задач линейного программирования // Вычислительные методы и программирование: новые вычислительные технологии. 2018. 19. 540-550.
  36. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical recipes: the art of scientific computing. New York: Cambridge Univ. Press, 2007.
  37. Censor Y., Elfving T., Herman G.T., Nikazad T. On diagonally relaxed orthogonal projection methods // SIAM Journal on Scientific Computing. 2008. 30, N 1. 473–504.
  38. Соколинский Л.Б., Соколинская И.М. Параллельный алгоритм решения нестационарных систем линейных неравенств // Параллельные вычислительные технологии — XIV международная конференция (ПаВТ’2020), г. Пермь, 31 марта–2 апреля 2020 г. Челябинск: Издательский центр ЮУрГУ, 2020. 275–286.
  39. Ежова Н.А., Соколинский Л.Б. BSF: модель параллельных вычислений для многопроцессорных систем с распределенной памятью // Параллельные вычислительные технологии — XII международная конференция, ПаВТ’2018, г. Ростов-на-Дону, 2–6 апреля 2018 г. Челябинск: Издательский центр ЮУрГУ, 2018. 253–265.
  40. Ежова Н.А., Соколинский Л.Б. Модель параллельных вычислений для многопроцессорных систем с распределенной памятью // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2018. 7, № 2. 32–49.
  41. Sokolinsky L.B. BSF-skeleton [Electronic resource]. 2019. https://github.com/leonid-sokolinsky/BSF-skeleton (accessed: 27.08.2020).
  42. Ежова Н.А., Соколинский Л.Б. Модель параллельных вычислений BSF-MR // Системы управления и информационные технологии. 2019. № 3. 15–21.
  43. Kostenetskiy P.S., Safonov A.Y. SUSU supercomputer resources // Proc. 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). CEURWorkshop Proceedings. Vol. 1576. 2016. 561-573.
  44. Gay D.M. Netlib-Lp [Electronic resource]. URL: http://www.netlib.org/lp/ (accessed: 27.08.2020).
  45. Koch T. The final NETLIB-LP results // Operations Research Letters. 2004. 32, N 2. 138–142.

Published

2020-09-27

How to Cite

Соколинский Л.Б., Соколинская И.М. 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" // Numerical methods and programming. 2020. 21. 329-340. doi 10.26089/NumMet.v21r328

Issue

Section

Parallel software tools and technologies