Tri-level optimization models to defend critical infrastructure
Loading...
Authors
San Martin, Pablo Alvarez
Subjects
Advisors
Wood, Kevin
Date of Issue
2007-09
Date
Publisher
Monterey California. Naval Postgraduate School
Language
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 85 p. : col. ill., col maps ;
Citation
Distribution Statement
Approved for public release; distribution is unlimited.