Accession Number:

ADA361997

Title:

System Interdiction and Defense.

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1999-03-01

Pagination or Media Count:

144.0

Abstract:

We study the problem of interdicting components of an adversarys system, e.g., a war-time economy, a transportation network, etc. Basic techniques are developed and illustrated with a simple network interdiction problem, maximizing the shortest path MXSP. In MXSP, an interdictor wishes to employ limited interdiction resources as effectively as possible to slow an adversary in moving between two network nodes. Interdiction destroys a network arc entirely or increases its effective length through an attack. This bi-level, max-mm problem is formulated as a mixed-integer program MIP, but unique decomposition algorithms are developed to solve the problem more efficiently than standard branch and bound. One algorithm is essentially Benders decomposition with special integrality cuts for the master problem. A second algorithm uses a new set-covering master problem, and a third is a hybrid of the first two. We extend our techniques i to solve general system-interdiction problems, some of which cannot be formulated as is, ii to solve system-defense problems where critical system components must be identified and hardened against interdiction, and iii to solve interdiction problems with uncertain interdiction success. We report computational experience for MXSP, a shortest-path network-defense problem and MXSP with uncertain interdiction success.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE