Tri-level optimization models to defend critical infrastructure

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.