Journal
INFORMS JOURNAL ON COMPUTING
Volume 28, Issue 3, Pages 527-539Publisher
INFORMS
DOI: 10.1287/ijoc.2016.0699
Keywords
stochastic network interdiction; chance constraint; mixed-integer programming; branch and cut; lifting
Categories
Funding
- National Science Foundation [CMMI-1433066]
- Directorate For Engineering [1433066] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn [1433066] Funding Source: National Science Foundation
Ask authors/readers for more resources
We consider a Stackelberg game in a network where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower's traveling distance is longer than a given threshold, interpreted by a chance constraint. Under the assumption of a wait-and-see follower-i.e., the follower selects a shortest path after seeing realizations of the random arc cost-we propose a branch-and-cut algorithm and apply lifting techniques to exploit the combinatorial structure of the risk-averse leader's interdiction problem. We demonstrate the computational efficacy of our approaches, risk-averse interdiction solution patterns, and result sensitivity, by testing instances of randomly generated grid networks and real-world transportation networks.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available