Tri-level optimization algorithms for solving defender-attacker- defender network models
Lazzaro, Gary L.
Carlyle, W. Matthew
MetadataShow full item record
The optimal defense and operation of networks against worst-case attack is an important problem for military analysts. We review development of existing solutions for the Defender-Attacker-Defender (DAD) tri-level optimization model and investigate new applications and solution procedures. We develop an implicit enumeration algorithm that incorporates addition of new defenses as an alternative solution method for the DAD model. Our testing demonstrates that implicit enumeration can efficiently generate all equivalent optimal or near-optimal solutions for DAD problems. When budgets for network defense or attack are uncertain, decision makers usually prioritize defenses in nested lists. We quantify the costs of various strategies for nesting of defenses. We design a parametric programming formulation of the DAD model to find nested defenses that have the smallest cost difference from optimal non-nested solutions. We create new solution procedures for the DAD constrained shortest path problem. We merge the attacker model with Lagrangian relaxation of the operator model into a single formulation that can obtain fast heuristic solutions. We combine our heuristic algorithm with traditional methods to obtain provably optimal or near-optimal solutions. We test our algorithms on medium and large networks, and our results show that our innovations can significantly outperform traditional nested decomposition.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Thomas, Adam J. (Monterey, California. Naval Postgraduate School, 2008-09);We develop the Game-Theoretic ASW Mission Planner (G-TAMP), an operational-level planning aid for the tasking of anti-submarine warfare (ASW) platforms to protect a high-value unit (HVU) from attack by hostile submarines ...
Brown, G.; Carlyle, M.; Diehl, D.; Kline, J.; Wood, K. (2005);We describe JOINT DEFENDER, a new two-sided optimization model for planning the pre-positioning of defensive missile interceptors to counter an attack threat. In our basic model, a defender pre-positions ballistic missile ...
Brown, Gerald G.; Carlyle, Matthew; Diehl, Douglas; Kline, Jeffrey; Wood, Kevin (2005);We describe JOINT DEFENDER, a new two-sided optimization model for planning the pre-positioning of defensive missile interceptors to counter an attack threat. In our basic model, a defender pre-positions ballistic missile ...