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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017060
Classification : 90C10, 90C11, 90C27, 90C47, 90C57, 90B06, 90B80
Mots-clés : Bilevel Programming, Branch-and-cut, The r-interdiction median problem with fortification
Roboredo, Marcos Costa 1 ; Pessoa, Artur Alves 1 ; Aizemberg, Luiz 1

1 
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2017060/

D. Aksen, N. Piyade and N. Aras, The budget constrained r-interdiction median problem with capacity expansion. Central Europ. J. Oper. Res. 18 (2010) 269–291. | MR | Zbl

D.L. Alderson, G.G. Brown, and W.M. Carlyle, Assessing and improving operational resilience of critical infrastructures and other systems. INFORMS Tutorials in Operations Research. Bridging Data and Decisions (2014) 180–215.

O. Alp, E. Erkut, and Z. Drezner, An efficient genetic algorithm for the p-median problem. Ann. Oper. Res. 122 (2003) 21–42. | MR | Zbl

J.F. Bard, and J.T. Moore, An algorithm for the discrete bilevel programming problem. Naval Research Logistics 39 (1992) 419–435. | MR | Zbl

G. Brown, M. Carlyle, J. Salmerón, and K. Wood, Defending critical infrastructure. Interfaces 36 (2006) 530–544.

R.L. Church, and M.P. Scaparra, Protecting critical assets: The r-interdiction median problem with fortification. Geographical Anal. 39 (2007) 129–146.

R.L. Church, M.P. Scaparra, and R.S. Middleton, 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).

M.F. Goodchild and V.T. Noronha, Location-allocation for small computers. Department of Geography, University of Iowa (1983).

E. Israeli and R.K. Wood, Shortest-path network interdiction Networks 40 (2002) 97–111. | MR | Zbl

T.L. Lei, Identifying critical facilities in hub-and-spoke networks: A hub interdiction median problem. Geographical Anal. 45 (2013) 105–122.

F. Liberatore, M.P. Scaparra and M.S. Daskin, 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

F. Liberatore, M.P. Scaparra and M.S. Daskin, Hedging against disruptions with ripple effects in location analysis. Omega 40 (2012) 21–30.

C. Losada, M.P. Scaparra and J.R. O’Hanley, Optimizing system resilience: a facility protection model with recovery time. Europ. J. Oper. Res. 217 (2012) 519–530. | MR | Zbl

J.T. Moore and J.F. Bard, The mixed integer linear bilevel programming problem. Oper. Res. 38 (1990) 911–921. | MR | Zbl

A.K. Nandi, H.R. Medal and S. Vadlamani, Interdicting attack graphs to protect organizations from cyber attacks: A bi-level defender–attacker model. Comput. Oper. Res. 75 (2016) 118–131. | MR | Zbl

J.R. O’Hanley and R.L. Church, 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).

M.C. Roboredo and A.A. Pessoa, A branch-and-cut algorithm for the discrete (r|p)-centroid problem. Europ. J. Operat. Res. 224 (2013) 101–109. | MR | Zbl

H. Sarhadi, D.M. Tulett and M. Verma, A defender-attacker-defender approach to the optimal fortification of a rail intermodal terminal network. J. Trans. Security 8 (2015) 17–32.

M.P. Scaparra and R.L. Church, An exact solution approach for the interdiction median problem with fortification. Europ. J. Oper. Res. 189 (2008) 76–92. | Zbl

M.P. Scaparra and R.L. Church, A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35 (2008) 1905–1923. | Zbl

L.V. Snyder, Z. Atan, P. Peng, Y. Rong, A.J. Schmitt and B. Sinsoysal, Or/ms models for supply chain disruptions: A review, IIE Trans. 48 (2016) 89–109.

Z.C. Taskn, J.C. Smith, S. Ahmed and A.J. Schaefer, Cutting plane algorithms for solving a stochastic edge-partition problem. Discrete Optim. 6 (2009) 420–435. | MR | Zbl

W. Yuan, L. Zhao and B. Zeng, Optimal power grid protection through a defender–attacker–defender model. Reliability Eng. Syst. Safety 121 (2014) 83–89.

Cité par Sources :