Stochastic Network Interdiction
Kelly J. Cormican, David P. Morton, R. Kevin Wood
Operations Research · 1998 · Volume 46 · Issue 2
Abstract
Using limited assets, an interdictor attempts to destroy parts of a capacitated network through which an adversary will subsequently maximize flow. We formulate and solve a stochastic version of the interdictor's problem: Minimize the expected maximum flow through the network when interdiction successes are binary random variables. Extensions are made to handle uncertain arc capacities and other realistic variations. These two-stage stochastic integer programs have applications to interdicting illegal drugs and to reducing the effectiveness of a military force moving materiel, troops, information, etc., through a network in wartime. Two equivalent model formulations allow Jensen's inequality to be used to compute both lower and upper bounds on the objective, and these bounds are improved within a sequential approximation algorithm. Successful computational results are reported on networks with over 100 nodes, 80 interdictable arcs, and 180 total arcs.
Keywords
Military, targeting, network interdiction, Programming, stochastic, sequential approximation, Networks graphs, stochastic, maximum flow
Enable JavaScript for citation tools and additional paper interactions.