Tri-level optimization models to defend critical infrastructure

Download
Author
San Martin, Pablo Alvarez
Date
2007-09Advisor
Wood, Kevin
Second Reader
Salmeron, Javier
Metadata
Show full item recordAbstract
This thesis develops and solves a tri-level optimization model to plan the optimal defense of an infrastructure from intelligent attack. We assume that a "defender" will first use limited defensive resources to protect system's components; then, an intelligent adversary ("attacker") will use limited offensive resources to attack unprotected components in order to inflict maximum damage to the system. The defender guides system operation with an optimization model, so increased operating cost equates to damage. This leads to a tri-level "defender-attackerdefender" model (DAD), where the second "defender" means "defender as system operator." The general DAD is NP-hard and requires decomposition to solve. We develop four decomposition algorithms: direct, nested, reformulation-based, and reordering-based. The reordering-based algorithm computes an optimistic bound by reordering the stages of the DAD, and the reformulation-based algorithm uses subproblems that resemble standard capacity-interdiction models. Computational tests on generic instances of "defending the shortest path" (DSP) show the nested and reformulation-based algorithms to be twice faster than the first, on average. A hypothetical instance of DSP provides a concrete illustration: A Spanish marine unit, in an emergency deployment, must defend its base-to-port route against potential terrorist attacks.
Collections
Related items
Showing items related by title, author, creator and subject.
-
DES-1 : an inter-active continuous system simulation language.
Kalashian, Michael Alex (Monterey, California. U.S. Naval Postgraduate School, 1969-06);There are strong tutorial advantages to Digital Computer Simulation of Control System's problems. This is particularly true where such simulations do not require sophisticated. programming techniques and where the user ... -
Analyzing the Vulnerability of Critical Infrastructure to Attack, and Planning Defenses
Brown, G.; Carlyle, W.M.; Salmeron, J.; Wood, K. (2005);We describe new bilevel programming models to (1) help make the country’s critical infrastructure more resilient to attacks by terrorists, (2) help governments and businesses plan those improvements, and (3) help influence ... -
Analyzing the Vulnerability of Critical Infrastructure to Attack, and Planning Defenses
Brown, G.; Carlyle, W.M.; Salmeron, J.; Wood, K. (2005);We describe new bilevel programming models (1) help make the country's critical infrastructure more resilient to attacks by terrorists (2) help governments and businesses plan those improvements, and (3) help influence ...