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

Utsav Sadana () and Erick Delage ()
Additional contact information
Utsav Sadana: GERAD, Montréal, Québec H3T 1J4, Canada; Desautels Faculty of Management, McGill University, Montréal, Québec H3A 1G5, Canada
Erick Delage: GERAD, Montréal, Québec H3T 1J4, Canada; Department of Decision Sciences, HEC Montréal, Montréal, Québec H3T 2A7, Canada

INFORMS Journal on Computing, 2023, vol. 35, issue 1, 216-232

Abstract: Conditional value at risk (CVaR) is widely used to account for the preferences of a risk-averse agent in extreme loss scenarios. To study the effectiveness of randomization in interdiction problems with an interdictor that is both risk- and ambiguity-averse, we introduce a distributionally robust maximum flow network interdiction problem in which the interdictor randomizes over the feasible interdiction plans in order to minimize the worst case CVaR of the maximum flow with respect to both the unknown distribution of the capacity of the arcs and the interdictor’s own randomized strategy. Using the size of the uncertainty set, we control the degree of conservatism in the model and reformulate the interdictor’s distributionally robust optimization problem as a bilinear 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 to obtain a 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 numerical experiments. Further, our numerical experiments show that randomized strategies can have significantly better performance than optimal deterministic ones.

Keywords: network interdiction; conditional value at risk; distributionally robust optimization; spatial branch and bound; column generation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1257 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:1:p:216-232

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().