Cell partition-based methods for stochastic shortest-path interdiction problems

We study a stochastic variant of a shortest-path interdiction game in which the interdictor attacks a subset of arcs in the network, followed by the evader traversing the network using a shortest source-sink path. The interdictor only knows the arc cost distributions when making the attacks, while the evader observes the real cost realizations when selecting a shortest path. As the number of cost scenarios is infinite and thus, enumerating all scenarios is not feasible, we investigate a cell-partition-based approach that iteratively refines the uncertainty space into subregions by splitting up arc cost distributions into smaller ranges. We apply bounding models to obtain bounds for each subregion on the evader’s shortest-path cost, from which the global bounds are also derived. These bounds become tighter as the uncertainty space gets further refined. We develop cutting plane algorithms based on different formulations and cell partition refinement strategies that exploit the problem structure. A single-cut formulation is developed and evaluated against the existing multi-cut formulation in the literature. While both formulations rely on the L-shaped decomposition to solve the interdictor’s problem, our single-cut formulation shows significant improvement in solution time compared to previously reported approaches.