Interdicting Stochastic Networks with Binary Interdiction Effort

Abstract

We provide formulations, test instances and benchmark results for a new class of network interdiction problems. The formulations are appropriate for computer, terrorist or drug transportation networks where the characteristics of the network cannot be known completely in advance but rather interdiction must be planned based on conjectured configurations. The models support maximization of the expected minimum path length between two nodes, s and t. We also model maximizing the probability of causing the minimum path length to be above a specified threshold. Examples make our formulations concrete and benchmarks establish the computational requirements for solution. Our benchmarks also help quantify the importance of using a special formulation provided for instances when a cut between s and t is the goal.