The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Inc., Upper Saddle River, NJ).Google Scholar
• Al-Khayyal FA, Falk JE (1983) Jointly constrained biconvex programming. Math. Oper. Res. 8(2):273–286.Link, Google Scholar
• Assimakopoulos N (1987) A network interdiction model for hospital infection control. Comput. Biol. Medicine 17(6):413–422.Crossref, Google Scholar
• Atamtürk A, Deck C, Jeon H (2020) Successive quadratic upper-bounding for discrete mean-risk minimization and network interdiction. INFORMS J. Comput. 32(2):346–355.Abstract, Google Scholar
• Bayraksan G, Love DK (2015) Data-driven stochastic programming using phi-divergences. The Operations Research Revolution, INFORMS TutORials in Operations Research, 1–19.Google Scholar
• Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming 88(3):411–424.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2008) Selected topics in robust convex optimization. Math. Programming 112(1):125–158.Crossref, Google Scholar
• Ben-Tal A, den Hertog D, Vial JP (2015) Deriving robust counterparts of nonlinear uncertain inequalities. Math. Programming 149(1):265–299.Crossref, Google Scholar
• Ben-Tal A, den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management Sci. 59(2):341–357.Link, Google Scholar
• Bertsimas D, Nasrabadi E, Orlin JB (2016) On the power of randomization in network interdiction. Oper. Res. Lett. 44(1):114–120.Crossref, Google Scholar
• Borrero JS, Prokopyev OA, Sauré D (2019) Sequential interdiction with incomplete information and learning. Oper. Res. 67(1):72–89.Link, Google Scholar
• Chandraker M, Kriegman D (2008) Globally optimal bilinear programming for computer vision applications. 2008 IEEE Conf. Comput. Vision Pattern Recognition (IEEE Computer Society, Anchorage, AK), 1–8.Google Scholar
• Chicoisne R, Ordóñez F, Espinoza D (2018) Risk averse shortest paths: A computational study. INFORMS J. Comput. 30(3):539–553.Link, Google Scholar
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• Delage E, Kuhn D, Wiesemann W (2019) “Dice”-sion-making under uncertainty: When can a random decision reduce risk? Management Sci. 65(7):3282–3301.Link, Google Scholar
• Delage E, Saif A (2021) The value of randomized solutions in mixed-integer distributionally robust optimization problems. INFORMS J. Comput. 34(1):333–353.Link, Google Scholar
• Desrosiers J, Lübbecke ME (2005) A primer in column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer US, Boston), 1–32.Crossref, Google Scholar
• Duchi JC, Glynn PW, Namkoong H (2021) Statistics of robust optimization: A generalized empirical likelihood approach. Math. Oper. Res. 46(3):946–969.Link, Google Scholar
• Ellsberg D (1961) Risk, ambiguity, and the savage axioms. Quart. J. Econom. 75(4):643–669.Crossref, Google Scholar
• Epstein LG (1999) A definition of uncertainty aversion. Rev. Econom. Stud. 66(3):579–608.Crossref, Google Scholar
• Hajinezhad D, Hong M (2019) Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization. Math. Programming 176(1):207–245.Crossref, Google Scholar
• Hajinezhad D, Shi Q (2018) Alternating direction method of multipliers for a class of nonconvex bilinear optimization: Convergence analysis and applications. J. Global Optim. 70(1):261–288.Crossref, Google Scholar
• Holzmann T, Smith JC (2021) The shortest path interdiction problem with randomized interdiction strategies: Complexity and algorithms. Oper. Res. 69(1):82–99.Link, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Jain M, Tsai J, Pita J, Kiekintveld C, Rathi S, Tambe M, Ordóñez F (2010) Software assistants for randomized patrol planning for the LAX airport police and the federal air marshal service. INFORMS J. Appl. Anal. 40(4):267–290.Link, Google Scholar
• Janjarassuk U, Linderoth J (2008) Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3):120–132.Crossref, Google Scholar
• Ji R, Lejeune MA (2021) Data-driven optimization of reward-risk ratio measures. INFORMS J. Comput. 33(3):1120–1137.Link, Google Scholar
• Lam H (2019) Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. Oper. Res. 67(4):1090–1105.Abstract, Google Scholar
• LeBlanc LJ, Morlok EK, Pierskalla WP (1975) An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Res. 9(5):309–318.Crossref, Google Scholar
• Lei X, Shen S, Song Y (2018) Stochastic maximum flow interdiction problems under heterogeneous risk preferences. Comput. Oper. Res. 90:97–109.Crossref, Google Scholar
• Liberti L, Pantelides CC (2006) An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Global Optim. 36(2):161–189.Crossref, Google Scholar
• Loizou N (2015) Distributionally robust game theory. Unpublished MSc thesis, Imperial College London.Google Scholar
• Magliocca NR, McSweeney K, Sesnie SE, Tellman E, Devine JA, Nielsen EA, Pearson Z, Wrathall DJ (2019) Modeling cocaine traffickers and counterdrug interdiction forces as a complex adaptive system. Proc. Natl. Acad. Sci. USA 116(16):7784–7792.Crossref, Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• McLay LA, Lloyd JD, Niman E (2011) Interdicting nuclear material on cargo containers using knapsack problem models. Ann. Oper. Res. 187(1):185–205.Crossref, Google Scholar
• Mohajerin Esfahani P, Kuhn D (2018) Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1):115–166.Crossref, Google Scholar
• Orlowski S, Wessäly R, Pióro M, Tomaszewski A (2010) SNDlib 1.0—Survivable network design library. Networks 55(3):276–286.Crossref, Google Scholar
• Pay BS, Merrick JR, Song Y (2019) Stochastic network interdiction with incomplete preference. Networks 73(1):3–22.Crossref, Google Scholar
• Postek K, den Hertog D, Melenberg B (2016) Computationally tractable counterparts of distributionally robust constraints on risk measures. SIAM Rev. 58(4):603–650.Crossref, Google Scholar
• Rockafellar R, Uryasev S (2000) Optimization of conditional value-at-risk. J. Risk 2(3):21–41.Crossref, Google Scholar
• Royset JO, Wood RK (2007) Solving the bi-objective maximum-flow network-interdiction problem. INFORMS J. Comput. 19(2):175–184.Link, Google Scholar
• Sherali HD, Alameddine A (1992) A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2(4):379–410.Crossref, Google Scholar
• Smith JC, Song Y (2020) A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3):797–811.Crossref, Google Scholar
• Smith JC, Prince M, Geunes J (2013) Modern network interdiction problems and algorithms. Pardalos PM, Du DZ, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 1949–1987.Crossref, Google Scholar
• Smith JE, Winkler RL (2006) The optimizer’s curse: Skepticism and postdecision surprise in decision analysis. Management Sci. 52(3):311–322.Link, Google Scholar
• Song Y, Shen S (2016) Risk-averse shortest path interdiction. INFORMS J. Comput. 28(3):527–539.Link, Google Scholar
• Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1–18.Crossref, Google Scholar
• Yang J, Borrero JS, Prokopyev OA, Sauré D (2021) Sequential shortest path interdiction with incomplete information and limited feedback. Decision Anal. 18(3):218–244.Abstract, Google Scholar