We study the r-interdiction median problem with fortification (RIMF), which considers demand points that are served by facilities. If a facility is interdicted, it can not serve any demand point, increasing the total system cost. To avoid an interdiction, a facility can be fortified. The problem consists of fortifying facilities knowing that some facilities will be interdicted. We propose a branch-and-cut algorithm for the RIMF and several experiments attest that our method outperforms the best exact algorithm found.
Accepté le :
DOI : 10.1051/ro/2017060
Mots-clés : Bilevel Programming, Branch-and-cut, The r-interdiction median problem with fortification
@article{RO_2019__53_2_505_0,
author = {Roboredo, Marcos Costa and Pessoa, Artur Alves and Aizemberg, Luiz},
title = {An exact approach for the r-interdiction median problem with fortification},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {505--516},
publisher = {EDP-Sciences},
volume = {53},
number = {2},
year = {2019},
doi = {10.1051/ro/2017060},
mrnumber = {3947644},
zbl = {1423.90149},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2017060/}
}
TY - JOUR AU - Roboredo, Marcos Costa AU - Pessoa, Artur Alves AU - Aizemberg, Luiz TI - An exact approach for the r-interdiction median problem with fortification JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 505 EP - 516 VL - 53 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2017060/ DO - 10.1051/ro/2017060 LA - en ID - RO_2019__53_2_505_0 ER -
%0 Journal Article %A Roboredo, Marcos Costa %A Pessoa, Artur Alves %A Aizemberg, Luiz %T An exact approach for the r-interdiction median problem with fortification %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 505-516 %V 53 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2017060/ %R 10.1051/ro/2017060 %G en %F RO_2019__53_2_505_0
Roboredo, Marcos Costa; Pessoa, Artur Alves; Aizemberg, Luiz. An exact approach for the r-interdiction median problem with fortification. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 505-516. doi : 10.1051/ro/2017060. http://archive.numdam.org/articles/10.1051/ro/2017060/
, and , The budget constrained r-interdiction median problem with capacity expansion. Central Europ. J. Oper. Res. 18 (2010) 269–291. | MR | Zbl
, , and , Assessing and improving operational resilience of critical infrastructures and other systems. INFORMS Tutorials in Operations Research. Bridging Data and Decisions (2014) 180–215.
, , and , An efficient genetic algorithm for the p-median problem. Ann. Oper. Res. 122 (2003) 21–42. | MR | Zbl
, and , An algorithm for the discrete bilevel programming problem. Naval Research Logistics 39 (1992) 419–435. | MR | Zbl
, , , and , Defending critical infrastructure. Interfaces 36 (2006) 530–544.
, and , Protecting critical assets: The r-interdiction median problem with fortification. Geographical Anal. 39 (2007) 129–146.
, , and , Identifying critical infrastructure: the median and covering facility interdiction problems. Ann. Association Amer. Geographers 94 (2004) 491–502.
Department of Homeland Security of the United States. Available at: https://www.dhs.gov/critical-infrastructure-sectors https://www.dhs.gov/critical-infrastructure-sectors (2019).
and , Location-allocation for small computers. Department of Geography, University of Iowa (1983).
and , Shortest-path network interdiction Networks 40 (2002) 97–111. | MR | Zbl
, Identifying critical facilities in hub-and-spoke networks: A hub interdiction median problem. Geographical Anal. 45 (2013) 105–122.
, and , Analysis of facility protection strategies against an uncertain number of attacks: the stochastic r-interdiction median problem with fortification. Comput. Oper. Res. 38 (2011) 357–366. | MR | Zbl
, and , Hedging against disruptions with ripple effects in location analysis. Omega 40 (2012) 21–30.
, and , Optimizing system resilience: a facility protection model with recovery time. Europ. J. Oper. Res. 217 (2012) 519–530. | MR | Zbl
and , The mixed integer linear bilevel programming problem. Oper. Res. 38 (1990) 911–921. | MR | Zbl
, and , Interdicting attack graphs to protect organizations from cyber attacks: A bi-level defender–attacker model. Comput. Oper. Res. 75 (2016) 118–131. | MR | Zbl
and , Designing robust coverage networks to hedge against worst-case facility losses. Europ. J. Oper. Res. 209 (2011) 23–36. | MR | Zbl
Passmark software. Available at: https://www.cpubenchmark.net (2019).
and , A branch-and-cut algorithm for the discrete (r|p)-centroid problem. Europ. J. Operat. Res. 224 (2013) 101–109. | MR | Zbl
, and , A defender-attacker-defender approach to the optimal fortification of a rail intermodal terminal network. J. Trans. Security 8 (2015) 17–32.
and , An exact solution approach for the interdiction median problem with fortification. Europ. J. Oper. Res. 189 (2008) 76–92. | Zbl
and , A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35 (2008) 1905–1923. | Zbl
, , , , and , Or/ms models for supply chain disruptions: A review, IIE Trans. 48 (2016) 89–109.
, , and , Cutting plane algorithms for solving a stochastic edge-partition problem. Discrete Optim. 6 (2009) 420–435. | MR | Zbl
, and , Optimal power grid protection through a defender–attacker–defender model. Reliability Eng. Syst. Safety 121 (2014) 83–89.
Cité par Sources :
