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

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

Авторы

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

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

линейное программирование
валидатор решений
VaLiPro
параллельный алгоритм
кластерные вычислительные системы
параллельный BSF каркас

Аннотация

В статье представлен параллельный алгоритм валидации решений задач линейного программирования. Идея метода состоит в том, чтобы генерировать регулярный набор точек на гиперсфере малого радиуса, центрированной в точке тестируемого решения. Целевая функция вычисляется для каждой точки валидационного множества, принадлежащей допустимой области. Если все полученные значения меньше или равны значению целевой функции в точке, проверяемой как решение, то эта точка считается корректным решением. Параллельная реализация алгоритма VaLiPro выполнена на языке C++ с использованием параллельного BSF-каркаса, инкапсулирующего в проблемно-независимой части своего кода все аспекты, связанные с распараллеливанием программы на базе библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе, подтверждающие эффективность предложенного подхода.

Загрузки

Опубликован

2021-11-06

Выпуск

Том 22 (2021): Выпуск 4.

Раздел

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

Авторы

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

Южно-Уральский государственный университет (национальный исследовательский университет),
просп. Ленина, 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). doi 10.1145/2611567.
  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. I. M. Sokolinskaya and L. B. Sokolinsky, “Study of the Scalability of the Apex Method for Solving Large-Scale Linear Programming Problems on Cluster Computing Systems,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 21-22, 2020 (MAKS Press, Moscow, 2020), pp. 49-59.
  5. 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.
    doi 10.1007/978-3-319-24024-4_17
  6. Q. Huangfu and J. A. J. Hall, “Parallelizing the Dual Revised Simplex Method,” Math. Prog. Comp. 10 (1), 119-142 (2018). doi 10.1007/s12532-017-0130-5.
  7. P. Tar, B. Stagel, and I. Maros, “Parallel Search Paths for the Simplex Algorithm,” Cent. Eur. J. Oper. Res. 25 (4), 967-984 (2017).
    doi 10.1007/s10100-016-0452-9
  8. L. Yang, T. Li, and J. Li, “Parallel Predictor-Corrector Interior-Point Algorithm of Structured Optimization Problems,” in Proc. 3rd Int. Conf. on Genetic and Evolutionary Computing, Gulin, China, October 14-17, 2009 (IEEE Press, New York, 2009), pp. 256-259.
    doi 10.1109/WGEC.2009.68
  9. D. M. Gay, “Electronic Mail Distribution of Linear Programming Test Problems,” Mathematical Programming Society COAL Newsletter 13, 10-12 (1985).
  10. A. Charnes, W. M. Raike, J. D. Stutz, et al., “On Generation of Test Problems for Linear Programming Codes,” Commun. ACM 17 (10), 583-586 (1974). doi 10.1145/355620.361173.
  11. J. L. Arthur and J. O. Frendewey, “GENGUB: A Generator for Linear Programs with Generalized upper Bound Constraints,” Comput. Oper. Res. 20 (6), 565-573 (1993).
    doi 10.1016/0305-0548(93)90112-V
  12. M. Dhiflaoui, S. Funke, C. Kwappik, et al., “Certifying and Repairing Solutions to Large LPs: How Good are LP-solvers?’’ in Proc. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, USA, January 12—14, 2003 (SIAM Press, Philadelphia, 2003), pp. 255-256.
    doi 10.5555/644108
  13. T. Koch, “The Final NETLIB-LP Results,” Oper. Res. Lett. 32 (2), 138-142 (2004).
    doi 10.1016/S0167-6377(03)00094-4
  14. D. L. Applegate, W. Cook, S. Dash, et al., “Exact Solutions to Linear Programming Problems,” Oper. Res. Lett. 35 (6), 693-699 (2007).
    doi 10.1016/j.orl.2006.12.010
  15. A. V. Panyukov and V. V. Gorbik, “Using Massively Parallel Computations for Absolutely Precise Solution of the Linear Programming Problems,” Avtom. Telemekh., No. 2, 73-88 (2012) [Autom. Rem. Contr. 73 (2), 276-290 (2012).
    doi 10.1134/S0005117912020063]
  16. A. M. Gleixner, D. E. Steffy, and K. Wolter, “Iterative Refinement for Linear Programming,” INFORMS J. Comput. 28 (3), 449-464 (2016).
    doi 10.1287/ijoc.2016.0692
  17. L. E. Blumenson, “A Derivation of n-Dimensional Spherical Coordinates,” Am. Math. Mon. 67 (1), 63-66 (1960).
    doi 10.2307/2308932
  18. L. B. Sokolinsky, “BSF: A Parallel Computation Model for Scalability Estimation of Iterative Numerical Algorithms on Cluster Computing Systems,” J. Parallel Distrib. Comput. 149, 193-206 (2021). doi 10.1016/j.jpdc.2020.12.009.
  19. S. Sahni and G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings,” J. Glob. Optim. 9 (3-4), 357-377 (1996).
    doi 10.1007/BF00121679
  20. R. S. Bird, “Lectures on Constructive Functional Programming,” in Constructive Methods in Computing Science (Springer, Heidelberg, 1988), Vol. 55, pp. 151-217.
  21. L. B. Sokolinsky, Parallel Algorithmic Skeleton BSF , Certificate of RF Registration of Computer Program No. 2 020 661 344.Date of Registration: September 22, 2020.
  22. L. B. Sokolinsky, “BSF-Skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems,” MethodsX 8 (2019).
    doi 10.1016/j.mex.2021.101437
  23. W. Gropp, “MPI 3 and Beyond: Why MPI is Successful and What Challenges It Faces,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2012), Vol. 7490, pp. 1-9.doi 10.1007/978-3-642-33518-1_1.
  24. P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computational Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. Vol. 1576, pp. 561-573 (2016).
    http://ceur-ws.org/Vol-1576/119.pdf
  25. I. M. Sokolinskaya and L. B. Sokolinsky, “On Generator of Random Problems for Linear Programming on Cluster Computing Systems,” Vestn. Yuzhn. Ural. Gos. Univ. Ser. Vychisl. Mat. Inf. 10 (2), 38-52 (2021).
    doi 10.14529/cmse210203

Лицензия

Copyright (c) 2021 Л.Б. Соколинский, И.М. Соколинская

Лицензия Creative Commons

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