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

DOI10.1287/IJOC.2022.1257MaRDI QIDQ6202875zbMATH OpenOpenAlexFDO

Authors Utsav Sadana, Erick Delage

Publication date 27 February 2024

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

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

zbMATH Keywords

column generationconditional value at riskdistributionally robust optimizationnetwork interdictionspatial branch-and-bound

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

• 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
• Optimal sequential stochastic shortest path interdiction
• Developing reward-risk aversion distributionally robust contract design models under ambiguous output probabilities
• Stochastic bilevel interdiction for fake news control in online social networks
• The sum of root-leaf distance interdiction problem with cardinality constraint by upgrading edges on trees
• Data-driven interdiction with asymmetric cost uncertainty: a distributionally robust optimization approach

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)