danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2018-62-2-147-150dan-501Research ArticleИНФОРМАТИКАINFORMATICSАБСОЛЮТНАЯ УСТОЙЧИВОСТЬ В ЗАДАЧАХ ОПТИМАЛЬНОГО ВЫБОРА С ФИКСИРОВАННЫМ ПРОШЛЫМABSOLUTE ROBUSTNESS FOR OPTIMAL SELECTION PROBLEMS WITH FIXED PASTКовалевМ. Я.KovalyovM. Ya.

член-корреспондент, д-р физ.-мат. наук, профессор, заместитель генерального директора по научной работе

Corresponding Member, D. Sc. (Physics and Mathematics), Professor, Deputy General Director for Research

kovalyov_my@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук Беларуси, МинскUnited Institute of Informatics Problems of the National Academy of Sciences of Belarus201820052018622147150Copyright © Ковалев М.Я., 20182018Ковалев М.Я.Kovalyov M.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/501

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

A novel approach to solving optimal selection problems under dynamic uncertainty is described. The approach is called absolute robustness with fixed past. An efficient algorithm is presented for the main problem and several its variants. The approach can be employed for solving other combinatorial optimization problems under dynamic uncertainty.

исследование операцийматематическое программированиеустойчивостьполиномиальный алгоритмoperations researchmathematical programmingrobustnesspolynomial algorithmReferencesRobust algorithms and price of robustness in shunting problems / S. Cicerone [et al.] // Proceedings of the 7th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS07). – Berlin, 2007. – P. 175–190.Cicerone S., D’Angelo G., Stefano G. D., Frigioni D., Navarra A. Robust algorithms and price of robustness in shunting problems. Proceedings of the 7th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS07). Berlin, 2007, pp. 175–190.Erera, A. L. Robust optimization for empty repositioning problems / A. L. Erera, J. C. Morales, M. Savelsbergh // Operations Research. – 2009. – Vol. 57, N 2. – P. 468–483. DOI: 10.1287/opre.1080.0650Erera A. L., Morales J. C., Savelsbergh M. Robust optimization for empty repositioning problems. Operations Research, 2009, vol. 57, no. 2, pp. 468–483. DOI: 10.1287/opre.1080.0650The concept of recoverable robustness, linear programming recovery, and railway applications / С. Liebchen [et al.] // Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. – Berlin: Springer, 2009. – P. 1–27. DOI: 10.1007/978-3-642-05465-5_1Liebchen С., Lubbecke M. E., Mohring R. H., Stiller S. The concept of recoverable robustness, linear programming recovery, and railway applications. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Berlin, Springer, 2009, pp. 1–27. DOI: 10.1007/978-3-642-05465-5_1Kasperski, A. Robust recoverable and two-stage selection problems / A. Kasperski, P. Zielinski // Discrete Applied Mathematics. – 2017. – Vol. 233. – P. 52–64. DOI: 10.1016/j.dam.2017.08.014Kasperski A., Zielinski P. Robust recoverable and two-stage selection problems. Discrete Applied Mathematics, 2017, vol. 233, pp. 52–64. DOI: 10.1016/j.dam.2017.08.014Bertsimas, D. Robust discrete optimization and network flows / D. Bertsimas, M. Sim // Mathematical Programming Series B. – 2003. – Vol. 98, N 1–3. – P. 49–71. DOI: 10.1007/s10107-003-0396-4Bertsimas D., Sim M. Robust discrete optimization and network flows. Mathematical Programming Series B, 2003, vol. 98, no. 1–3, pp. 49–71. DOI: 10.1007/s10107-003-0396-4Time bounds for selection / M. Blum [et al.] // Journal of Computer and Systems Sciences. – 1973. – Vol. 7, N 4. – P. 448–461. DOI: 10.1016/s0022-0000(73)80033-9Blum M., Floyd R. W., Pratt V., Rivest R. L., Tarjan R. E. Time bounds for selection. Journal of Computer and Systems Sciences, 1973, vol. 7, no. 4, pp. 448–461. DOI: 10.1016/s0022-0000(73)80033-9

The authors declare that there are no conflicts of interest present.