Parallel implementation of the simplex method in matrix form using the PyTorch library for economics and management problems
Abstract
The simplex method is widely used in economic planning and forecasting tasks. However, this method is used in real economic activity to find solutions to large-scale tasks, the speed of which is not a critical factor. This significantly limits the applied value of the simplex method in the economic sphere, since currently there is a certain tendency to move to more detailed economic models, which makes it urgent to accelerate calculations based on the simplex method. In these conditions, GPU (Graphical Processor Unit) computing accelerators become the most important means of accelerating calculations. The authors propose the implementation of the simplex method in matrix form for computing on GPUs using the PyTorch library. This allows you to switch to using the computing power of graphics processors in a simple and reliable way. A linear programming problem with 900 constraints is solved on a graphics accelerator 6–9 times faster than the solution on a conventional processor. This paper identifies groups of applied economic problems for which the proposed algorithms and methods can be relevant.
Downloads
References
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).
