Multilevel Approaches for the Critical Node Problem
成果类型：
Article
署名作者：
Baggio, Andrea; Carvalho, Margarida; Lodi, Andrea; Tramontani, Andrea
署名单位：
Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2020.2014
发表日期：
2021
页码：
486-508
关键词：
摘要：
In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious viral attacks. On the one hand, network safety is investigated from a preventive perspective. On the other hand, blocking models have been proposed for scenarios in which the attack has already taken place causing a harmful spreading throughout the network. In this work, we combine these two perspectives. More precisely, following the framework defender-attacker-defender, we consider a model of prevention, attack, and damage containment using a three-stage, zero-sum game. The defender is not only able to adopt preventive strategies, but also to defend the network after an attack takes place. Assuming that the attacker acts optimally, we compute a defensive strategy for the first stage that minimizes the total damage to the network in the end of the third stage. Our contribution consists of considering this problem as a trilevel mixed-integer program and designing an exact algorithm for it based on tools developed for multilevel programming.