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

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

Работа рекомендована Программным комитетом международной конференции «Суперкомпьютерные дни в России»

Авторы

  • Л.Б. Соколинский
  • И.М. Соколинская

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

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

Аннотация

Статья посвящена исследованию нового метода решения сверхбольших задач линейного программирования. Указанный метод получил название "апекс-метод". Апекс-метод работает по схеме предиктор-корректор. На фазе предиктор находится точка, лежащая на границе n-мерного многогранника, задающего допустимую область задачи линейного программирования. На фазе корректор организуется итерационный процесс, в результате которого строится последовательность точек, сходящаяся к точному решению задачи линейного программирования. В статье дается формальное описание апекс-метода и приводятся сведения о его параллельной реализации на языке C++ с использованием библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе по исследованию масштабируемости апекс-метода.

Новые вычислительные технологии

Загрузки

Опубликован

2020-09-27

Выпуск

Том 21 (2020): Выпуск 3.

Раздел

Параллельные программные средства и технологии

Авторы

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

Южно-Уральский государственный университет (национальный исследовательский университет),
просп. Ленина, 76, 454080, Челябинск
• профессор, проректор

И.М. Соколинская

Южно-Уральский государственный университет (национальный исследовательский университет),
просп. Ленина, 76, 454080, Челябинск
• доцент

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

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

Лицензия

Copyright (c) 2020 Вычислительные методы и программирование

Лицензия Creative Commons

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