Stochastic Network Interdiction

Kelly J. Cormican, David P. Morton and R. Kevin Wood
Additional contact information
Kelly J. Cormican: Naval Postgraduate School, Monterey, California
David P. Morton: The University of Texas at Austin, Austin, Texas
R. Kevin Wood: Naval Postgraduate School, Monterey, California

Operations Research, 1998, vol. 46, issue 2, 184-197

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 (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (77)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.2.184 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:2:p:184-197

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().