Accession Number : ADA297596

Title :   Computational Methods for Deterministic and Stochastic Network Interdiction Problems.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Cormican, Kelly J.

PDF Url : ADA297596

Report Date : MAR 1995

Pagination or Media Count : 75

Abstract : 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. (KAR) P. 2

Descriptors :   *INTERDICTION, *MATHEMATICAL PROGRAMMING, *COMMUNICATIONS NETWORKS, *NETWORK FLOWS, *DRUG INTERDICTION, MATHEMATICAL MODELS, ALGORITHMS, SCENARIOS, COMPUTATIONS, STOCHASTIC PROCESSES, PROBABILITY, SITES, ATTACK, THESES, TIME, SUPPLY DEPOTS, AERIAL WARFARE, MILITARY APPLICATIONS, USER NEEDS, HEURISTIC METHODS, RESOURCES, ENEMY, NUMERICAL METHODS AND PROCEDURES, DECOMPOSITION, DETERMINANTS(MATHEMATICS).

Subject Categories : Operations Research
      Computer Systems
      Military Operations, Strategy and Tactics

Distribution Statement : APPROVED FOR PUBLIC RELEASE