Stochastic Network Interdiction
- 1 April 1998
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 46 (2), 184-197
- https://doi.org/10.1287/opre.46.2.184
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.This publication has 23 references indexed in Scilit:
- Measures of vulnerability–the integrity familyNetworks, 1994
- Stochastic Two-Stage ProgrammingPublished by Springer Science and Business Media LLC ,1992
- Sublinear upper bounds for stochastic programs with recourseMathematical Programming, 1989
- A Separable Piecewise Linear Upper Bound for Stochastic Linear ProgramsSIAM Journal on Control and Optimization, 1988
- Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recoursePublished by Springer Science and Business Media LLC ,1986
- Bounds on expected performance of networks with links subject to failureNetworks, 1984
- Vulnerability of communication networksNetworks, 1984
- The value of the stochastic solution in stochastic linear programs with fixed recourseMathematical Programming, 1982
- Maximal expected flow in a network subject to arc failuresNetworks, 1980
- Maximum flow in probabilistic graphs‐the discrete caseNetworks, 1976