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

Николай Александрович Ольховский,Леонид Борисович Соколинский

ПРЕПРИНТ

Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.

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

Н. А. Ольховский,

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

2023-10-13

https://doi.org/10.24108/preprints-3112762

В статье представлен новый итерационный метод линейного программирования, получивший название ``метод поверхностного движения''. Данный метод строит на поверхности многогранника, ограничивающего допустимую область задачи линейного программирования, путь от начальной граничной точки до точки, в которой достигается оптимальное значение целевой функции. Вектор движения строится в направлении максимального увеличения/уменьшения значения целевой функции. Представлено формальное описание алгоритма, реализующего метод поверхностного движения. Доказана теорема сходимости. Описанный метод предполагает использование глубокой нейронной сети прямого распространения для определения направления движения по граням допустимого многогранника. Для этого строится многомерный локальный образ задачи линейного программирования в точке текущего приближения, который подается на вход нейронной сети. Множество размеченных прецедентов, необходимое для обучения нейронной сети может быть получено с помощью апекс-метода.

Ссылка для цитирования:

Ольховский Н. А., Соколинский Л. Б. 2023. О новом методе линейного программирования с использованием нейронных сетей. PREPRINTS.RU. https://doi.org/10.24108/preprints-3112762

Список литературы

1. Hartung T. Making Big Sense from Big Data // Frontiers in Big Data. 2018. Vol. 1. P. 5. doi 10.3389/fdata.2018.00005.

2. Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии (ПаВТ’2017). Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. C. 471–484. http://omega.sp.susu.ru/pavt2017/short/014.pdf.

3. Branke J. Optimization in Dynamic Environments // Evolutionary Optimization in Dynamic Environments. Genetic Algorithms and Evolutionary Computation, vol. 3. Boston, MA: Springer, 2002. P. 13–29. doi 10.1007/978-1-4615-0911-0_2.

4. Ерёмин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. М.: Наука. Главная редакция физико-математической литературы, 1979. 288 с.

5. Brogaard J., Hendershott T., Riordan R. High-Frequency Trading and Price Discovery // Review of Financial Studies. 2014. Vol. 27, no. 8. P. 2267–2306. doi 10.1093/rfs/hhu032.

6. Deng S., Huang X., Wang J., et al. A Decision Support System for Trading in Apple Futures Market Using Predictions Fusion // IEEE Access. 2021. Vol. 9. P. 1271–1285. doi 10.1109/ACCESS.2020.3047138.

7. Seregin G. Lecture notes on regularity theory for the Navier-Stokes equations. Singapore:World Scientific Publishing Company, 2014. 268 p. doi 10.1142/9314.

8. Demin D.A. Synthesis of optimal control of technological processes based on a multialternative parametric description of the final state // Eastern-European Journal of Enterprise Technologies. 2017. Vol. 3, 4(87). P. 51–63. doi 10.15587/1729-4061.2017.105294.

9. Kazarinov L.S., Shnayder D.A., Kolesnikova O.V. Heat load control in steam boilers // 2017 International Conference on Industrial Engineering, Applications and Manufacturing, ICIEAM 2017 - Proceedings. IEEE, 2017. doi 10.1109/ICIEAM.2017.8076177.

10. Zagoskina E.V., Barbasova T.A., Shnaider D.A. Intelligent Control System of Blast-furnace Melting Ffiency // SIBIRCON 2019 - International Multi-Conference on Engineering, Computer and Information Sciences, Proceedings. IEEE, 2019. P. 710–713. doi 10.1109/SIBIRCON48586.2019.8958221.

11. Fleming J., Yan X., Allison C., et al. Real-time predictive eco-driving assistance considering road geometry and long-range radar measurements // IET Intelligent Transport Systems. 2021. Vol. 15, no. 4. P. 573–583. doi 10.1049/ITR2.12047.

12. Scholl M., Minnerup K., Reiter C., et al. Optimization of a thermal management system for battery electric vehicles // 14th International Conference on Ecological Vehicles and Renewable Energies, EVER 2019. IEEE, 2019. doi 10.1109/EVER.2019.8813657.

13. Meisel S. Dynamic Vehicle Routing // Anticipatory Optimization for Dynamic Decision Making. Operations Research/Computer Science Interfaces Series, vol. 51. New York, NY: Springer, 2011. P. 77–96. doi 10.1007/978-1-4614-0505-4_6.

14. Kiran D Production Planning and Control: A Comprehensive Approach. Elsevier Inc., 2019. 582 p. doi 10.1016/C2018-0-03856-6.

15. Mall R. Real-Time Systems: Theory and Practice. Delhi, India: Pearson Education, 2007. 242 p.

16. Dantzig G.B. Linear programming and extensions. Princeton, N.J.: Princeton university press, 1998. 656 p.

17. Hall J., McKinnon K. Hyper-sparsity in the revised simplex method and how to exploit it // Computational Optimization and Applications. 2005. Vol. 32, no. 3. P. 259–283. doi 10.1007/s10589-005-4802-0.

18. Klee V., Minty G. How good is the simplex algorithm? // Inequalities - III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1-9, 1969 / ed. by O. Shisha. New York-London: Academic Press, 1972. P. 159–175.

19. Bartels R., Stoer J., Zenger C. A Realization of the Simplex Method Based on Triangular Decompositions // Handbook for Automatic Computation. Volume II: Linear Algebra. Berlin, Heidelberg: Springer, 1971. P. 152–190. doi 10.1007/978-3-642-86940-2_11.

20. Tolla P. A Survey of Some Linear Programming Methods // Concepts of Combinatorial Optimization / ed. by V.T. Paschos. 2nd ed. Hoboken, NJ, USA: John Wiley, Sons, 2014. Chap. 7. P. 157–188. doi 10.1002/9781119005216.ch7.

21. Hall J. Towards a practical parallelisation of the simplex method // Computational Management Science. 2010. Vol. 7, no. 2. P. 139–170. doi 10.1007/s10287-008-0080-5.

22. Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method // Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295 / ed. by C. Zaroliagis, G. Pantziou, S. Kontogiannis. Cham: Springer, 2015. P. 281–307. doi 10.1007/978-3-319-24024-4_17.

23. Зоркальцев В.И., Мокрый И.В. Алгоритмы внутренних точек в линейной оптимизации // Сибирский журнал индустриальной математики. 2018. Т. 21, 1 (73). C. 11–20. doi 10.17377/sibjim.2018.21.102.

24. Дикин И.И. Итеративное решение задач линейного и квадратичного программирования // Доклады Академии наук СССР. 1967. Т. 174, № 4. C. 747–748. https://www.mathnet.ru/rus/dan33112.

25. Gondzio J. Interior point methods 25 years later // European Journal of Operational Research. 2012. Vol. 218, no. 3. P. 587–601. doi 10.1016/j.ejor.2011.09.017.

26. Roos C., Terlaky T., Vial J.-P. Interior Point Methods for Linear Optimization. New York: Springer, 2005. 500 p. doi 10.1007/b100325.

27. Sokolinskaya I.M. Parallel Method of Pseudoprojection for Linear Inequalities // Parallel Computational Technologies. PCT 2018. Communications in Computer and Information Science, vol. 910 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2018. P. 216–231. doi 10.1007/978-3-319-99673-8_16.

28. Gondzio J., Grothey A. Direct Solution of Linear Systems of Size 109 Arising in Optimization with Interior Point Methods // Parallel Processing and Applied Mathematics. PPAM 2005. Lecture Notes in Computer Science, vol. 3911. 3911 LNCS / ed. by R. Wyrzykowski, J. Dongarra, N. Meyer, J. Wasniewski. Berlin, Heidelberg: Springer, 2006. P. 513–525. doi 10.1007/11752578_62.

29. Prieto A., Prieto B., Ortigosa E.M., et al. Neural networks: An overview of early research, current frameworks and new challenges // Neurocomputing. 2016. Vol. 214. P. 242–268. doi 10.1016/j.neucom.2016.06.014.

30. Tank D.W., Hopfield J.J. Simple ‘neural’ optimization networks: An A/D converter, signal decision circuit, and a linear programming circuit // IEEE transactions on circuits and systems. 1986. Vol. CAS–33, no. 5. P. 533–541. doi 10.1109/TCS.1986.1085953.

31. Kennedy M.P., Chua L.O. Unifying the Tank and Hopfield Linear Programming Circuit and the Canonical Nonlinear Programming Circuit of Chua and Lin // IEEE Transactions on Circuits and Systems. 1987. Vol. 34, no. 2. P. 210–214. doi 10.1109/TCS.1987.1086095.

32. Rodriguez-Vazquez A., Dominguez-Castro R., Rueda A., et al. Nonlinear Switched-Capacitor “Neural” Networks for Optimization Problems // IEEE Transactions on Circuits and Systems. 1990. Vol. 37, no. 3. P. 384–398. doi 10.1109/31.52732.

33. Zak S.H., Upatising V. Solving Linear Programming Problems with Neural Networks: A Comparative Study // IEEE Transactions on Neural Networks. 1995. Vol. 6, no. 1. P. 94–104. doi 10.1109/72.363446.

34. Malek A., Yari A. Primal-dual solution for the linear programming problems using neural networks // Applied Mathematics and Computation. 2005. Vol. 167, no. 1. P. 198–211. doi 10.1016/J.AMC.2004.06.081.

35. Liu X., Zhou M. A one-layer recurrent neural network for non-smooth convex optimization subject to linear inequality constraints // Chaos, Solitons and Fractals. 2016. Vol. 87. P. 39–46. doi 10.1016/j.chaos.2016.03.009.

36. LeCun Y., Bengio Y., Hinton G. Deep learning // Nature. 2015. Vol. 521, no. 7553. P. 436–444. doi 10.1038/nature14539.

37. Ольховский Н.А., Соколинский Л.Б. Визуальное представление многомерных задач линейного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. C. 31–56. doi 10.14529/cmse220103.

38. Raina R., Madhavan A., Ng A.Y. Large-scale deep unsupervised learning using graphics processors // Proceedings of the 26th Annual International Conference on Machine Learning (ICML ’09). New York, NY, USA: ACM Press, 2009. P. 873–880. doi 10.1145/1553374.1553486.

39. Соколинский Л.Б., Соколинская И.М. О новой версии апекс-метода для решения задач линейного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 2. С. 5–46. doi 10.14529/cmse230201.

ПРЕПРИНТ

ИНФОРМАЦИЯ