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

DOI10.1287/IJOC.2022.1257arXiv2003.07915OpenAlexW4311705215MaRDI QIDQ6202875FDOQ6202875

Authors: Utsav Sadana, Erick Delage 

Publication date: 27 February 2024

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: Conditional Value at Risk (CVaR) is widely used to account for the preferences of a risk-averse agent in the extreme loss scenarios. To study the effectiveness of randomization in interdiction games with an interdictor that is both risk and ambiguity averse, we introduce a distributionally robust network interdiction game where the interdictor randomizes over the feasible interdiction plans in order to minimize the worst-case CVaR of the flow with respect to both the unknown distribution of the capacity of the arcs and his mixed strategy over interdicted arcs. The flow player, on the contrary, maximizes the total flow in the network. By using the budgeted uncertainty set, we control the degree of conservatism in the model and reformulate the interdictor's non-linear problem as a bi-convex optimization problem. For solving this problem to any given optimality level, we devise a spatial branch and bound algorithm that uses the McCormick inequalities and reduced reformulation linearization technique (RRLT) to obtain convex relaxation of the problem. We also develop a column generation algorithm to identify the optimal support of the convex relaxation which is then used in the coordinate descent algorithm to determine the upper bounds. The efficiency and convergence of the spatial branch and bound algorithm is established in the numerical experiments. Further, our numerical experiments show that randomized strategies can have significantly better in-sample and out-of-sample performance than optimal deterministic ones.

Full work available at URL: https://arxiv.org/abs/2003.07915

Recommendations

• Distributionally risk‐receptive and risk‐averse network interdiction problems with general ambiguity set
• On the power of randomization in network interdiction
• Stochastic maximum flow interdiction problems under heterogeneous risk preferences
• The Value of Randomized Solutions in Mixed-Integer Distributionally Robust Optimization Problems
• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms

zbMATH Keywords

column generationconditional value at risknetwork interdictiondistributionally robust optimizationspatial branch-and-bound

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Robustness in mathematical programming (90C17)

Cited In (2)

• Distributionally risk‐receptive and risk‐averse network interdiction problems with general ambiguity set
• Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption

This page was built for publication: The Value of Randomized Strategies in Distributionally Robust Risk-Averse Network Interdiction Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202875)