Computational methods for deterministic and stochastic network interdiction problems
Cormican, Kelly James
Wood, R. Kevin
Morton, David P.
MetadataShow full item record
Using limited resources, a network interdictor attempts to disable components of a capacitated network with the objective of minimizing the maximum network flow achievable by the network user. This problem has applications to reducing the importation of illegal drugs and planning wartime air attacks against an enemy's supply lines. A deterministic model using Benders decomposition is developed and improved upon with an original "flow-dispersion heuristic." An extension is made to accommodate probabilistic scenarios, where each scenario is an estimate of uncertain arc capacities in the actual network. A unique sequential- approximation algorithm is utilized to investigate cases where interdiction successes are binary random variables. For a network of 3200 nodes and 6280 arcs, Benders decomposition solves the network interdiction problem in less than one-third of the time required by a direct branch-and-bound method. The flow-dispersion heuristic can decrease solution time to one-fifth or less of that required for the Benders decomposition algorithm alone. With six allowable but uncertain interdictions in a network of 100 nodes and 84 possible interdiction sites among 180 arcs, a stochastic network interdiction problem is solved to optimality in 24 minutes on a IBM RISC/6000 Model 590. With uncertain arc capacities in five scenarios, and three allowable and certain interdictions, a 900 node and 1740 arc network is solved to optimality in 17 minutes on a 60MHZ Pentium PC.
RightsThis 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.
Showing items related by title, author, creator and subject.
Bingol, Levent (Monterey, California. Naval Postgraduate School, 2001-12);This thesis is concerned with solving or approximately solving a maximum-flow network-interdiction problem denoted MXFI: A network user strives to maximize flow of a commodity through a capacitated network, while an ...
DeWolfe, Dean; Stevens, James; Wood, R. Kevin (1993);The United States military frequently has difficulty retaining enlisted personnel beyond their initial enlistment. A bonus program within each service, called a Selective Reenlistment Bonus (SRB) program, seeds to enhance ...
Salmeron, Javier; Wood, R. Kevin; Baldick, Ross (Monterey, California. Naval Postgraduate School, 2004); NPS-OR-04-001This research extends our earlier work to improve the security of electric power grids subject to disruptions caused by terrorist attacks. To identify critical system components (e.g., transmission lines, generators, ...