Multilevel Approaches for the Critical Node Problem

Andrea Baggio (), Margarida Carvalho (), Andrea Lodi () and Andrea Tramontani ()
Additional contact information
Andrea Baggio: Quant Research, swissQuant Group AG, CH-8001 Zurich, Switzerland;
Margarida Carvalho: CIRRELT and DIRO, Université de Montréal, Montréal, Québec H3T 1J4, Canada;
Andrea Lodi: École Polytechnique de Montréal, Montreal, Québec H3T 1J4, Canada;
Andrea Tramontani: CPLEX Optimization, IBM, 40132 Bologna, Italy

Operations Research, 2021, vol. 69, issue 2, 486-508

Abstract: 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.

Keywords: multilevel programming; critical node problem; firefighter problem; mixed-integer programming; defender–attacker–defender (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2014 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:2:p:486-508

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().