Tri-level optimization models to defend critical infrastructure
San Martin, Pablo Alvarez
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...