Optimization Online


Distributionally risk-receptive and risk-averse network interdiction problems with general ambiguity set

Sumin Kang (suminkang***at***vt.edu)
Manish Bansal (bansal***at***vt.edu)

Abstract: In this paper, we introduce generalizations of stochastic network interdiction problem with distributional ambiguity. In particular, we consider a distributionally risk-averse (or robust) network interdiction problem (DRA-NIP) and a distributionally risk-receptive network interdiction problem (DRR-NIP) where a leader maximizes a follower's minimal expected objective value for either the worst-case or the best-case, respectively, probability distribution belonging to a given set of distributions (referred to as ambiguity set). The DRA-NIP arises in applications where a risk-averse leader is the main protagonist who interdicts a follower (opponent or evader) to cause delays in their supply convoy. In contrast, the DRR-NIP is applicable for network vulnerability analysis where a network user (or follower) also seeks to identify vulnerabilities in the network against potential disruptions by an adversary (or leader) who is receptive to risk for improving the expected objective values. We present exact and approximation algorithms for solving DRA-NIP and DRR-NIP with a general ambiguity set. We also provide conditions and family of ambiguity sets for which these approaches are finitely convergent. To evaluate the effectiveness and efficiency of the approaches for solving DRA-NIP and DRR-NIP, we provide results of our extensive computational experiments performed on instances known in the literature for (risk-neutral) stochastic NIP.

Keywords: stochastic network interdiction, distributionally robust optimization, distributionally risk-receptive, decomposition algorithm, general ambiguity set

Category 1: Stochastic Programming

Category 2: Network Optimization

Citation: SKMB1, Virginia Tech, Dec 2021.

Download: [PDF]

Entry Submitted: 12/16/2021
Entry Accepted: 12/17/2021
Entry Last Modified: 05/14/2022

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society