System interdiction and defense
Abstract
We study the problem of interdicting components of an adversary's 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
Collections
Related items
Showing items related by title, author, creator and subject.
-
Two-person zero-sum network-interdiction game with multiple inspector types
Unsal, Omur (Monterey, California. Naval Postgraduate School, 2010-06);Wood (1995) to handle multiple types of interdiction assets (e.g., aircraft, ground-based inspection teams), referred to here as "inspectors." A single evader attempts to traverse a path between two vertices in a directed ... -
Computational methods for deterministic and stochastic network interdiction problems
Cormican, Kelly James (Monterey, California. Naval Postgraduate School, 1995-03);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 ... -
Deterministic Network Interdiction
Wood, R.K. (1993);Interest in network interdiction has been rekindled because of attempts to reduce the flow of drugs and precursor chemicals through river and road networks in South America. This paper considers a problem in which an enemy ...