STOCHASTIC NETWORK INTERDICTION

Using limited assets, an interdictor attempts to destroy parts of a ca pacitated network through which an adversary will subsequently maximiz e flow. We formulate and solve a stochastic version of the interdictor 's problem: Minimize the expected maximum flow through the network whe n interdiction successes are binary random variables. Extensions are m ade to handle uncertain are capacities and other realistic variations. These two-stage stochastic integer programs have applications to inte rdicting illegal drugs and to reducing the effectiveness of a military force moving materiel, troops, information, etc., through a network i n wartime. Two equivalent model formulations allow Jensen's inequality to be used to compute both lower and upper bounds on the objective, a nd these bounds are improved within a sequential approximation algorit hm. Successful computational results are reported on networks with ove r 100 nodes, 80 interdictable arcs, and 180 total arcs.