Multilevel Approaches for the Critical Node Problem
Andrea Baggio, Margarida Carvalho, Andrea Lodi, Andrea Tramontani
Abstract
Multilevel programming can provide the right mathematical formulations for modeling sequential decision-making problems. In such cases, it is implicit that each level anticipates the optimal reaction of the subsequent ones. Defender–attacker–defender trilevel programs are a particular case of interest that encompasses a fortification strategy, followed by an attack, and a consequent recovery defensive strategy. In “Multilevel Approaches for the Critical Node Problem,” Baggio, Carvalho, Lodi, and Tramontani study a combinatorial sequential game between a defender and an attacker that takes place in a network. The authors propose an exact algorithmic framework. This work highlights the significant improvements that the defender can achieve by taking the three-stage game into account instead of considering fortification and recovery as isolated. Simultaneously, the paper contributes to advancing the methodologies for solving trilevel programs.