×

On the multistage shortest path problem under distributional uncertainty. (English) Zbl 1517.90094

Summary: In this paper, we consider an ambiguity-averse multistage network game between a user and an attacker. The arc costs are assumed to be random variables that satisfy prescribed first-order moment constraints for some subsets of arcs and individual probability constraints for some particular arcs. The user aims at minimizing its cumulative expected loss by traversing between two fixed nodes in the network, while the attacker’s objective is to maximize the user’s expected loss by selecting a distribution of arc costs from the family of admissible distributions. In contrast to most of the related studies, both the user and the attacker can dynamically adjust their decisions at particular nodes of the user’s path. By observing the user’s decisions, the attacker may reveal some additional distributional information associated with the arcs emanated from the current user’s position. It is shown that the resulting multistage distributionally robust shortest path problem (DRSPP) admits a linear mixed-integer programming reformulation (MIP). In particular, we distinguish between acyclic and general graphs by introducing different forms of non-anticipativity constraints. Finally, we perform a numerical study, where the quality of adaptive decisions and computational tractability of the proposed MIP reformulation are explored with respect to several classes of synthetic network instances.

MSC:

90C17 Robustness in mathematical programming
90C27 Combinatorial optimization
90C47 Minimax problems in mathematical programming

Software:

ROME

References:

[1] Asudegi, M.; Haghani, A., Optimal number and location of node-based sensors for collection of travel time data in networks, Transp. Res. Rec., 2338, 1, 35-43 (2013) · doi:10.3141/2338-05
[2] Bayraksan, G., Love, D.K.: Data-driven stochastic programming using phi-divergences. In: The Operations Research Revolution, INFORMS, pp. 1-19 (2015)
[3] Bertsimas, D.; Dunning, I., Multistage robust mixed-integer optimization with adaptive partitions, Oper. Res., 64, 4, 980-998 (2016) · Zbl 1348.90624 · doi:10.1287/opre.2016.1515
[4] Bertsimas, D.; Georghiou, A., Design of near optimal decision rules in multistage adaptive mixed-integer optimization, Oper. Res., 63, 3, 610-627 (2015) · Zbl 1327.90126 · doi:10.1287/opre.2015.1365
[5] Bertsimas, D.; Sim, M.; Zhang, M., Adaptive distributionally robust optimization, Manag. Sci., 65, 2, 604-618 (2018) · doi:10.1287/mnsc.2017.2952
[6] Birge, JR; Louveaux, F., Introduction to Stochastic Programming (2011), Berlin: Springer, Berlin · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[7] Borrero, JS; Prokopyev, OA; Sauré, D., Sequential shortest path interdiction with incomplete information, Decis. Anal., 13, 1, 68-98 (2015) · Zbl 1398.91165 · doi:10.1287/deca.2015.0325
[8] Borrero, JS; Prokopyev, OA; Sauré, D., Sequential interdiction with incomplete information and learning, Oper. Res., 67, 1, 72-89 (2019) · Zbl 1443.90206 · doi:10.1287/opre.2018.1773
[9] Bubeck, S., Cesa-Bianchi, N., Kakade, S.M.: Towards minimax policies for online linear optimization with bandit feedback. In: Mannor, S., Srebro, N., Williamson, R.C. (eds.), Conference on Learning Theory, pp. 41.1-41.14 (2012)
[10] Buchheim, C.; Kurtz, J., Robust combinatorial optimization under convex and discrete cost uncertainty, EURO J. Comput. Optim., 6, 3, 211-238 (2018) · Zbl 1417.90125 · doi:10.1007/s13675-018-0103-0
[11] Cao, Z., Guo, H., Zhang, J., Niyato, D., Fastenrath, U.: A data-driven method for stochastic shortest path problem. In: 17th International IEEE Conference on Intelligent Transportation Systems (ITSC), IEEE, pp. 1045-1052 (2014)
[12] Chassein, A.; Dokka, T.; Goerigk, M., Algorithms and uncertainty sets for data-driven robust shortest path problems, Eur. J. Oper. Res., 274, 2, 671-686 (2019) · Zbl 1404.90131 · doi:10.1016/j.ejor.2018.10.006
[13] Cheng, J.; Leung, J.; Lisser, A., New reformulations of distributionally robust shortest path problem, Comput. Oper. Res., 74, 196-204 (2016) · Zbl 1349.90808 · doi:10.1016/j.cor.2016.05.002
[14] Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C., Introduction to Algorithms (2009), Cambridge: MIT Press, Cambridge · Zbl 1187.68679
[15] Delage, E.; Kuhn, D.; Wiesemann, W., “Dice”-sion-making under uncertainty: when can a random decision reduce risk?, Manag. Sci., 65, 7, 3282-3301 (2019) · doi:10.1287/mnsc.2018.3108
[16] Delage, E.; Saif, A., The value of randomized solutions in mixed-integer distributionally robust optimization problems, INFORMS J. Comput., 34, 1, 333-353 (2022) · Zbl 07549381 · doi:10.1287/ijoc.2020.1042
[17] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58, 3, 595-612 (2010) · Zbl 1228.90064 · doi:10.1287/opre.1090.0741
[18] Esfahani, PM; Kuhn, D., Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations, Math. Program., 171, 1-2, 115-166 (2018) · Zbl 1433.90095 · doi:10.1007/s10107-017-1172-1
[19] Gavriel, C., Hanasusanto, G., Kuhn, D.: Risk-averse shortest path problems. In: 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), IEEE, pp. 2533-2538 (2012)
[20] Goh, J.; Sim, M., Distributionally robust optimization and its tractable approximations, Oper. Res., 58, 4-1, 902-917 (2010) · Zbl 1228.90067 · doi:10.1287/opre.1090.0795
[21] Gupta, AK; Nadarajah, S., Handbook of Beta Distribution and its Applications (2004), Boca Raton: CRC Press, Boca Raton · Zbl 1062.62021 · doi:10.1201/9781482276596
[22] Haghani, A.; Hamedi, M.; Sadabadi, KF; Young, S.; Tarnoff, P., Data collection of freeway travel time ground truth with bluetooth sensors, Transp. Res. Rec., 2160, 1, 60-68 (2010) · doi:10.3141/2160-07
[23] Hanasusanto, GA; Kuhn, D.; Wiesemann, W., K-adaptability in two-stage distributionally robust binary programming, Oper. Res. Lett., 44, 1, 6-11 (2016) · Zbl 1408.90210 · doi:10.1016/j.orl.2015.10.006
[24] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 301, 13-30 (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[25] Isii, K., On sharpness of Tchebycheff-type inequalities, Ann. Inst. Stat. Math., 14, 1, 185-197 (1962) · Zbl 0245.60014 · doi:10.1007/BF02868641
[26] Jiang, R.; Guan, Y., Risk-averse two-stage stochastic program with distributional ambiguity, Oper. Res., 66, 5, 1390-1405 (2018) · Zbl 1455.90114 · doi:10.1287/opre.2018.1729
[27] Ketkov, SS; Prokopyev, OA, On greedy and strategic evaders in sequential interdiction settings with incomplete information, Omega, 92, 102161 (2020) · doi:10.1016/j.omega.2019.102161
[28] Ketkov, SS; Prokopyev, OA; Burashnikov, EP, An approach to the distributionally robust shortest path problem, Comput. Oper. Res., 130, 105212 (2021) · Zbl 1510.90279 · doi:10.1016/j.cor.2021.105212
[29] Khanjani-Shiraz, R.; Babapour-Azar, A.; Hosseini-Noudeh, Z.; Pardalos, PM, Distributionally robust maximum probability shortest path problem, J. Comb. Optim., 43, 1, 140-167 (2021) · Zbl 1485.90082 · doi:10.1007/s10878-021-00747-9
[30] Kreinovich, V.; Xiang, G.; Starks, SA; Longpré, L.; Ceberio, M.; Araiza, R.; Beck, J.; Kandathi, R.; Nayak, A.; Torres, R.; Hajagos, JG, Towards combining probabilistic and interval uncertainty in engineering calculations: algorithms for computing statistics under interval uncertainty, and their computational complexity, Reliab. Comput., 12, 6, 471-501 (2006) · Zbl 1104.65010 · doi:10.1007/s11155-006-9015-4
[31] Miller, CE; Tucker, AW; Zemlin, RA, Integer programming formulation of traveling salesman problems, J. ACM (JACM), 7, 4, 326-329 (1960) · Zbl 0100.15101 · doi:10.1145/321043.321046
[32] Postek, K.; Hertog, D., Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set, INFORMS J. Comput., 28, 3, 553-574 (2016) · Zbl 1348.90507 · doi:10.1287/ijoc.2016.0696
[33] Rockafellar, RT; Uryasev, S., Optimization of conditional value-at-risk, J. Risk, 2, 21-42 (2000) · doi:10.21314/JOR.2000.038
[34] Sefair, JA; Smith, JC, Dynamic shortest-path interdiction, Networks, 68, 4, 315-330 (2016) · Zbl 1390.90124 · doi:10.1002/net.21712
[35] Shapiro, A.; Goberna, MA; Lopez, MA, On duality theory of conic linear problems, Semi-Infinite Programming, 135-165 (2001), Boston: Springer, Boston · Zbl 1055.90088 · doi:10.1007/978-1-4757-3403-4_7
[36] Sun, J., The Statistical Analysis of Interval-censored Failure Time Data (2006), Berlin: Springer, Berlin · Zbl 1127.62090
[37] Taccari, L., Integer programming formulations for the elementary shortest path problem, Eur. J. Oper. Res., 252, 1, 122-130 (2016) · Zbl 1346.90793 · doi:10.1016/j.ejor.2016.01.003
[38] Vo, T.: An investigation of bluetooth technology for measuring travel times on arterial roads: a case study on spring street. Dissertation, Georgia Institute of Technology (2011)
[39] Wang, Z.; You, K.; Song, S.; Zhang, Y., Wasserstein distributionally robust shortest path problem, Eur. J. Oper. Res., 284, 1, 31-43 (2020) · Zbl 1441.90113 · doi:10.1016/j.ejor.2020.01.009
[40] Wiesemann, W.; Kuhn, D.; Sim, M., Distributionally robust convex optimization, Oper. Res., 62, 6, 1358-1376 (2014) · Zbl 1327.90158 · doi:10.1287/opre.2014.1314
[41] Wolsey, LA; Nemhauser, GL, Integer and Combinatorial Optimization (1999), New York: Wiley, New York · Zbl 0944.90001
[42] Xu, H.; Mannor, S.; Lafferty, J.; Williams, C.; Shawe-Taylor, J.; Zemel, R.; Culotta, A., Distributionally robust Markov decision processes, Advances in Neural Information Processing Systems 23 (NIPS 2010) (2010), New York: Curran Associates Inc., New York
[43] Yu, X.; Shen, S., Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets, Math. Program., 196, 1-2, 1025-1064 (2022) · Zbl 1506.90176 · doi:10.1007/s10107-020-01580-4
[44] Zhang, Y.; Song, S.; Shen, ZJM; Wu, C., Robust shortest path problem with distributional uncertainty, IEEE Trans. Intell. Transp. Syst., 19, 4, 1080-1090 (2017) · doi:10.1109/TITS.2017.2709798
[45] Zou, J.; Ahmed, S.; Sun, XA, Stochastic dual dynamic integer programming, Math. Program., 175, 1-2, 461-502 (2019) · Zbl 1412.90101 · doi:10.1007/s10107-018-1249-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.