Stochastic Network Interdiction

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...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1998-03, Vol.46 (2), p.184-197
Main Authors: Cormican, Kelly J, Morton, David P, Wood, R. Kevin
Format: Article
Language:English
Subjects:
Algorithms
Applications
Applied sciences
Approximation
Approximation algorithms
Determinism
Drug trafficking
Error rates
Exact sciences and technology
Flows in networks. Combinatorial problems
Integer programming
Integers
Mathematical programming
maximum flow
Military
Military strategy
network interdiction
Networks graphs
Operational research and scientific management
Operational research. Management science
Operations research
Programming
Random variables
Research grants
sequential approximation
stochastic
Stochastic models
Studies
targeting
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.46.2.184