Stochastic Network Interdiction
Authors
Cormican, K.J.
Morton, D.P.
Wood, R.K.
Subjects
Network Interdiction and Attacker-Defender Modeling
Advisors
Date of Issue
1998
Date
1998
Publisher
Language
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.
Type
Description
Operations Research, 46, pp. 184‐197.
Center for Infrastructure Defense (CID) Paper.
Center for Infrastructure Defense (CID) Paper.
Series/Report No
Department
Department of Operations Research
Organization
Center for Infrastructure Defense (CID)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Cormican, K.J., Morton, D.P. and Wood, R.K., 1998, “Stochastic Network Interdiction,” Operations Research, 46, pp. 184‐197.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.