Stochastic network interdiction

Kelly J. Cormican*, David P. Morton, R. Kevin Wood

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

200 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)184-197
Number of pages14
JournalOperations Research
Volume46
Issue number2
DOIs
StatePublished - 1998

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Stochastic network interdiction'. Together they form a unique fingerprint.

Cite this