Параллельная реализация симплекс-метода в матричной форме средствами библиотеки PyTorch для задач экономики и менеджмента
Аннотация
Симплекс-метод имеет широкое применение в задачах экономического планирования и прогнозирования. Однако, этот метод используется в реальной экономической деятельности для поиска решения масштабных задач, скорость выполнения процедур которых не является критичным фактором. Это в существенной степени ограничивает прикладное значение симплекс-метода в экономической сфере, поскольку в настоящее время сформировалась определенная тенденция перехода к более подробным экономическим моделям, что делает актуальной задачу ускорения расчетов на основе симплекс-метода. В этих условиях важнейшим средством ускорения расчетов становятся графические ускорители вычислений GPU (Graphical Processor Unit). Авторами предлагается реализация симплекс-метода в матричной форме для вычислений на графических процессорах средствами библиотеки PyTorch, которая позволяет перейти к использованию вычислительных мощностей графических процессоров простым и надежным способом. Задача линейного программирования с 900 ограничениями решается на графическом ускорителе в 6–9 раз быстрее по сравнению с решением на обычном процессоре. В работе выделены группы прикладных экономических задач, для которых предложенные алгоритмы и методы могут быть актуальны.
Скачивания
Литература
Kanorovich L.V. (1939) Mathematical methods of organization and planning of production. Leningrad: Leningrad State University Press (in Russian).
Makarov V.L., Bakhtizin A.R., Sushko E.D., Sushko G.B. (2022) Creating a supercomputer simulation of society with active agents of different types and its testing. Herald of the Russian Academy of Sciences, vol. 92, no. 5, pp. 458–466 (in Russian).
Kolev M., Georgiadou S. (2022) On simulation and modeling in economics. Asian-European Journal of Mathematics, vol. 15, no. 10, article 2250239. https://doi.org/10.1142/s1793557122502394
Davydov I., Kochetov Yu., Tolstykh D., et al. (2023) Hybrid variable neighborhood search for automated warehouse scheduling. Optimization Letters, vol. 17, no. 9, pp. 2185–2199. https://doi.org/10.1007/s11590-022-01921-6
Chistyakova T.B., Shashikhina O.E. (2022) Intelligent software complex for modeling the process of planning multi-assortment industrial productions. Applied Informatics, vol. 17, no. 5(101), pp. 41–50 (in Russian). https://doi.org/10.37791/2687-0649-2022-17-5-41-50
Beklaryan L.A., Beklaryan G.L., Akopov A.S., Khachatryan N.K. (2024) Dynamic and agent-based models of intelligent transport systems. Economics and Mathematical Methods, vol. 60, no. 2, pp. 105–122 (in Russian). https://doi.org/10.31857/S0424738824020091
Mochurad L., Boyko N., Sheketa V. (2020) Parallelization of the method of simulated annealing when solving multicriteria optimization problems. Proceedings of the CEUR Workshop, Lviv, May 21, 2020, pp. 12–24.
Arrow K.J. (2008) George Dantzig in the development of economic analysis. Discrete Optimization, vol. 5, no. 2, pp. 159–167. https://doi.org/10.1016/j.disopt.2006.11.007
Ratushnyi A., Kochetov Y. (2021) A column generation based heuristic for a temporal bin packing problem. Proceedings of the 20th International Conference Mathematical Optimization Theory and Operations Research (MOTOR 2021) (eds. P. Pardalos, M. Khachay, A. Kazakov), Irkutsk, Russia, July 5–10, 2021. Lecture Notes in Computer Science, vol. 12755, pp. 96–110. Springer, Cham. https://doi.org/10.1007/978-3-030-77876-7_7
Kochetov Yu.A., Shamray N.B. (2021) Optimization of placement and relocation of emergency medical teams. Discrete Analysis and Operation Research, vol. 28, no. 2(148), pp. 5–34 (in Russian). https://doi.org/10.33048/daio.2021.28.702
Kovesnikov V.A., Mehtiev A.Ya. (2020) Study of the accumulative-sorting method for solving parametric optimization problems. Control Issues, no. 2, pp. 28–35 (in Russian). https://doi.org/10.25728/pu.2020.2.3
Manne A.S. (1958) A linear programming model of the U.S. petroleum refining industry. Econometrica, no. 26, pp. 67–196.
Chenery H.B. (1949) Engineering production functions. The Quarterly Journal of Economics, no. 63, pp. 507–531.
Makarov V.L., Bakhtizin A.R., Beklaryan G.L., Akopov A.S. (2021) Digital plant: methods of discrete-event modeling and optimization of production characteristics. Business Informatics, vol. 15, no. 2, pp. 7–20. https://doi.org/10.17323/2587-814X.2021.2.7.20
Scarf H.E. (1990) Mathematical programming and economic theory. Operations Research, vol. 38, no. 3, pp. 377–385.
Apalkova T.G., Kosorukov O.A., Mishchenko A.V., Tsourkov V.I. (2024) Mathematical models for managing the production and financial activities of an enterprise. Herald of the Russian Academy of Sciences. Theory and Systems of Control, no. 2, pp. 107–129. https://doi.org/10.31857/S0002338824020109
Gergel V., Grishagin V., Liniov A., Shumikhin S. (2021) Parallel computations in integrated environment of engineering modeling and global optimization. Proceedings of the 16th International Conference (PaCT 2021), Kaliningrad, Russia, September 13–18, 2021 (ed. V. Malyshkin), Lecture Notes in Computer Science, vol. 12942, pp. 413–419. Springer, Cham. https://doi.org/10.1007/978-3-030-86359-3_31
Gergel V., Kozinov E. (2021) Parallel computations for solving multicriteria mixed-integer optimization problems. Communications in Computer and Information Science, vol. 1437, pp. 92–107. https://doi.org/10.1007/978-3-030-81691-9_7
Shichkina Y., Kupriyanov M., Awadh AM.M.H. (2020) Application of methods for optimizing parallel algorithms for solving problems of distributed computing systems. Proceedings of the International Conference on Cyber-Physical Systems and Control (CPS&C'2019), St. Petersburg, Russia, June 10–12, 2019 (eds. D. Arseniev, L. Overmeyer, H. Kälviäinen, B. Katalinić), Lecture Notes in Networks and Systems, vol. 95, pp. 212–224. Springer, Cham. https://doi.org/10.1007/978-3-030-34983-7_21
Makarov V.L., Bakhtizin A.R., Beklaryan G.L., Akopov A.S., Strelkovskii N.V. (2022) Simulation of migration and demographic processes using FLAME GPU. Business Informatics, vol. 16, no. 1, pp. 7–21. https://doi.org/10.17323/2587-814X.2022.1.7.21
Beklaryan A.L., Akopov A.S., Beklaryan L.A. (2021) Implementation of the Deffuant model within the FLAME GPU framework. Advances in Systems Science and Applications, vol. 21, no. 4, pp. 87–99. https://doi.org/10.25728/assa.2021.21.4.1161
Coutinho D.A.M., Lins e Silva F.O., Aloise D., Xavier-de-Souza S. (2019) A scalable shared-memory parallel simplex for large-scale linear programming. arXiv:1804.04737v2. https://doi.org/10.48550/arXiv.1804.04737
Mochurad L. (2020) Parallelization of the Simplex method based on the OpenMP technology. Proceedings of the 4th International Conference on Computational Linguistics and Intelligent Systems (COLINS 2020), Lviv, Ukraine, April 23–24, 2020, pp. 952–963.
Hall J.A.J. (2010) Towards a practical parallelization of the Simplex method. Computational Management Science, vol. 7, pp. 139–170. https://doi.org/10.1007/s10287-008-0080-5
Bieling J. (2010) An efficient GPU implementation of the revised simplex method. Proceedings of the IEEE International Symposium on Parallel Distributed Processing, Workshops and PhD Forum (IPDPSW), Atlanta, GA, USA, pp. 1–8. https://doi.org/10.1109/IPDPSW.2010.5470831
Bazaraa M.S., Jarvis J.J., Sherali H.D. (2010) Linear Programming and Network Flows. Hoboken, NJ: John Wiley & Sons, Inc.
Instituto Superior Técnico, Universidade de Lisboa (2025) LP random problem generator. Available at: https://web.tecnico.ulisboa.pt/~mcasquilho/compute/or/Fx-LP-generator.php (accessed 20 April 2025).
