Dynamic programming in applied tasks which are allowing to reduce the options selection

The article discusses the dynamic programming algorithm developed by R. Bellman, based on the search for the optimal trajectory connecting the nodes of a predefined regular grid of states. Possibilities are analyzed for a sharp increase in the effectiveness of using dynamic programming in solving applied problems with specific features, which allows us to refuse to split a regular grid of states and implement an algorithm for finding the optimal trajectory when rejecting not only unpromising options for paths leading to each of the states, and all of them continuations, as in R. Bellmanʼs algorithm, but also actually hopeless states and all variants of paths emanating from them. The conditions are formulated and justified under which the rejection of hopeless states is possible. It has been established that many applied problems satisfy these conditions. To solve such problems, a new dynamic programming algorithm described in the article is proposed and implemented. Concrete examples of such applied problems are given: the optimal distribution of a homogeneous resource between several consumers, the optimal loading of vehicles, the optimal distribution of finances when choosing investment projects. To solve these problems, dynamic programming algorithms with rejecting unpromising paths, but without rejecting states, were previously proposed. The number of hopeless states that appear at various stages of dynamic programming and, accordingly, the effectiveness of the new algorithm depends on the specific numerical values of the source data. For the two-parameter problem of optimal loading of vehicles with weight and volume constraints, the results of comparative calculations by the R. Bellman algorithm and the new dynamic programming algorithm are presented. As a source of data for a series of calculations, pseudorandom numbers were used. As a result of the analysis, it was shown that the comparative efficiency of the algorithm with rejection of states increases with increasing dimension of the problem. So, in the problem of the optimal choice of items for loading a vehicle of a given carrying capacity with a number of items of 150, the number of memorized states and the counting time are reduced by 50 and 57 times, respectively, when using the new algorithm compared to the classical algorithm of R. Bellman. And for 15 items, the corresponding numbers are 13 and 4.

dynamic programming, objective function, optimal trajectory, rejection of states

1. Bellman R. Dinamicheskoe programmirovanie (Dynamic programming). Moscow: Inostrannaya literatura Publ., 1960. 402 p. (in Russ.).

2. Lyakhovskii V.N., Mikhalevich V.S., Bykov V.I. Determination on the computer of the most advantageous position of the red line of the longitudinal profile on the free run. Transportnoe stroitel'stvo = Transport Construction. 1962;4:41-43.

3. Mikhalevich V.S., Shor N.Z. The mathematical foundations of solving the problem of choosing the optimal outline of the longitudinal profile. Trudy Vsesoyuznogo NII transportnogo stroitel'stva = Proceedings of the Institute of Transport Construction. 1964;51:12-24 (in Russ.).

4. Mikhalevich V.S. Sequential optimization algorithms and their application. Kibernetika. 1965;1:45-56 (in Russ.).

5. Mikhalevich V.S., Bykov V.I., Sibirko A.N. To the question of designing the optimal longitudinal profile of the road. Transportnoe stroitel'stvo = Transport Construction. 1975;6:39-40 (in Russ.).

6. Kosmin V.V., Struchenkov V.I., Fradkov E.B. Computeraided longitudinal road profile design. Transportnoe stroitel'stvo = Transport Construction. 1971;4:38-42 (in Russ.).

7. Bellman R., Dreifus S. Prikladnye zadachi dinamicheskogo programmirovaniya (Applied problems of dynamic programming). Moscow: Nauka; 1965. 460 p. (in Russ.).

8. Lezhnev A.V. Dinamicheskoe programmirovanie v ekonomicheskikh zadachakh (Dynamic programming in economic problems). Moscow: Binom; 2016. 176 p.

9. Kremer N.Sh. Issledovanie operatsii v ekonomike (The study of operations in the economy). Moscow: Yurait; 2012. 430 р. ISBN 978-5-9916-1849-6

10. Cavagnari G., Marigonda A., Piccoli B. Generalized dynamic programming principle and sparse meanfield control problems. J. Math. Anal. Appl. 2020;481(1): Article No. 123437. https://doi.org/10.1016/j.jmaa.2019.123437

11. Ramahatana F., David M. Economic optimization of micro-grid operations by dynamic programming with real energy forecast. J. Phys. Conf. 2019;1343(1): Article No. 012067. https://doi.org/10.1088/1742-6596/1343/1/012067

12. Firdausiyah N., Taniguchi E., Qureshi A.G. Impacts of Urban Consolidation Centres for Sustainable City Logistics Using Adaptive Dynamic Programming Based MultiAgent Simulation. In: IOP Conference Series: Earth and Environmental Science. 2019;328(1): Article No. 012071. https://doi.org/10.1088/1755-315/328/1/012071

13. He S., Shin H.-S., Tsourdos A. Computational guidance using sparse Gauss-Hermite quadrature differential dynamic programming. IFAC-PapersOnLine. 2019;52(12):13-18. https://doi.org/10.1016/j.ifacol.2019.11.062

14. He S., Guo S., Chen, K., Deng L., Liao Z., Xiong F., Yin J. Dataset for reservoir impoundment operation coupling parallel dynamic programming with importance sampling and successive approximation. Data in Brief. 2019;26: Article No. 104440. https://doi.org/10.1016/j.dib.2019.104440

15. Fayaed S.S., Fiyadh S.S., Khai W.J., Ahmed A.N., Afan H.A., Ibrahim R.K. Improving dam and reservoir operation rules using stochastic dynamic programming and artificial neural network integration model. Sustainability. 2019;11(19):5367. https://doi.org/10.3390/su11195367

16. Işik H., Sintunavarat W. An investigation of the common solutions for coupled systems of functional equations arising in dynamic programming. Mathematics. 2019;7(10):977. https://doi.org/10.3390/math7100977

17. Jia S., Sun J.Q., Ding Q. Flutter Control of a Two-dimensional Airfoil based on Adaptive Dynamic Programming. In: IOP Conference Series: Materials Science and Engineering. 2019;531(1): Article No. 012033. https://doi.org/10.1088/1757-899X/531/1/012033

18. Kozlowski K.M., Sharma G.K., Chen J.J., Qi L., Osann K., Jing J.C., Ahuja G.S. Dynamic programming and automated segmentation of optical coherence tomography images of the neonatal subglottis: Enabling efficient diagnostics to manage subglottic stenosis. J. Biomed. Opt. 2019;24(9):096001. https://doi.org/10.1117/1.JBO.24.9.096001

19. Durdán, M., Kačur, J., Laciak, M., Flegner, P. Thermophysical properties estimation in annealing process using the iterative dynamic programming method and gradient method. Energies. 2019;12(17):3267. https://doi.org/10.3390/en12173267

20. Wang P., Peng Y., Gao X.-J., Gao H.-H. Train Speed Trajectory Optimization using Dynamic Programming with speed modes decomposition. In: IOP Conference Series: Materials Science and Engineering. 2019;569(4):042019. https://doi.org/10.1088/1757-899X/569/4/042019

21. Ikeda S. Ooka, R. Comparison of metaheuristics and dynamic programming for district energy optimization. In: IOP Conference Series: Earth and Environmental Science. 2019:294(1):9. https://doi.org/10.1088/1755-1315/294/1/012040

22. Narendra Kumar P.V., Chengaiah C., Prasad J.V.K. Fuzzy dynamic programming based solarthermal load scheduling of Andhra Pradesh power generation using Matlab. International Journal of Recent Technology and Engineering (IJRTE). 2019;8(2S8):1242-1247. https://doi.org/10.35940/ijrte.B1046.0882S819

23. Karpov D.A., Struchenkov V.I. Dynamic Programming as a Method of Spline Approxi-mation in the CAD Systems of Linear Constructions. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2019;7(3):77-88 (in Russ.). https://doi.org/10.32362/2500-316X-2019-7-3-77-88

24. Romanovskii I.V. Diskretnyi analiz (Discrete analysis). St. Petersburg: Nevskii Dialekt, BKhV–Peterburg; 2003. 320 р. (in Russ.). ISBN 5-7940-0114-3

25. Venttsel՚ E.S. Issledovanie operatsii: zadachi, printsipy, metodologiya (Operations research: tasks, principles, methodology). Moscow: KnoRus; 2010. 191 р. (in Russ.). ISBN 978-5-406-00682-5

26. Kosorukov O.A., Mishchenko A.V. Issledovanie operatsii: Uchebnik dlya vuzov (Operations Research). Moscow: Ekzamen; 2013. 445 p. (in Russ.). ISBN 5-94692-363-3

27. Struchenkov V.I. The use of parabolic splinees in CAD of linear structures. Rossiiskii tekhnologicheskii zhurnal = Russian Technological Journal. 2018;6(1):40-52 (in Russ.). https://doi.org/10.32362/2500-316X-2018-6-1-40-52