Bi-level Multiple Attack Type Protection Models for Defense Planning of Critical Systems

Year 2021, Volume: 36 Issue: 4, 1909 - 1922, 02.09.2021

Orkun Başkan Müjgan Sağır

https://doi.org/10.17341/gazimmfd.615372

Abstract

Critical facilities are highly important for a country.
Damage the facilities as a result of war, terrorist attack, natural disasters
etc., the country is affected significantly. Protection of these facilities is
one of the major problems. Especially with the 11 September 2001 attack and
terrorist attacks of EU countries, many studies have started in the USA, EU and
other developed countries for the security of critical facilities.

 

This paper is one of NP hard facility protection problems
and determines which facilities are to be protected to meet the demand of a
particular zone. In previous studies, different attack and defence types have
been disregarded for this problem.  This
paper presents two new mathematical models for defense planning of critical
systems . Our models consider different attack and defense options. The
decision of which facilities under the risk of different attacks are to be
protected to meet the demand of a particular zone is of interest. Also
preferential aim to disrupt the supply-demand balance are included in the
model.

 

Solution of problem has based RIMF (r-interdiction median
problem with fortification) model of Scaparra (2008). First model proposed is called as  which considers these different
attack and defense types and decides the best protection strategy, second model
is called as  and this model tries to disrupt
the supply-demand balance. Due to the security reasons, obtaining real data for
such problems are almost impossible. Therefore we generate test data to use
models. We obtain results but for bigger sized problems, a heuristic approach
is needed and we are working on that.

Keywords

Interdiction problem, protection problem, bi-level programing, defense planning, attack types, supply-demand balance

Kritik sistemlerin savunma planlaması için iki seviyeli çoklu saldırı tipli koruma modelleri

Abstract

Kritik tesisler, bir ülke için yüksek önem düzeyine
sahip, herhangi bir sebeple savaş, terörist saldırı, doğal afetler vb. gibi
kendilerine verilecek zarar neticesinde, ülkeyi önemli ölçüde etkileyebilecek
tesislerdir. Bu tesislerin korunması önemli problemlerden biridir. Özellikle 11
Eylül 2001’deki ve AB ülkelerinde gerçekleşen terör saldırıları ile birlikte
kritik tesislerin güvenliğine yönelik ABD, AB ve gelişmiş diğer ülkelerde pek
çok çalışma başlamıştır.

 

Bu çalışma belirli bir bölgenin talebinin kesintisiz
olarak sağlanması için hangi tesislerin korunacağının belirlenmesine yönelik
ele alınan NP zor sınıftaki tesis koruma problemlerinden biri ile ilgilidir. Bu
çalışmada kritik sistemlerin savunma planlaması için iki yeni matematiksel
model sunulmuştur. Bu modeller, daha önceki çalışmalarda göz ardı edilmiş olan
farklı saldırı tipleri ve karşı gelen savunma tipleri göz önüne alınmıştır.
Ayrıca sınırlı kaynaklara sahip sistemler için Arz Talep dengesinin bozulmasına
yönelik öncelikli amaç modele dahil edilmiştir.

 

Problemin çözümü için, Scaparra (2008)’nın RIMF
(r-interdiction median problem with fortification) modeli temel alınmıştır. İlk
model saldırı ve koruma tiplerini göz önüne alan ve eniyi koruma stratejisini
veren iki seviyeli  modelidir, ikinci model arz talep
dengesini bozma amaçlı saldırıların göz önüne alındığı  modelidir. Çeşitli güvelik
sebebleri ile gerçek verilere ulaşmak güçtür, bu nedenle modellerin testi için
üretilen test verileri ile modeller eniyi çözümü vermiştir. Ancak daha büyük
ölçekli problemler için sezgisel bir yaklaşım gerekmektedir ve bunun üzerinde
çalışmaktayız.

Keywords

Yasaklama problemleri, koruma problemleri, iki seviyeli programlama, savunma planlaması, saldırı tipleri, arz-talep dengesi

References

• Scaparra M.P., Church R.L., An exact solution approach for the interdiction median problem with fortification, European Journal of Operational Research 189 (2008) 76–92, 2008.
• Stackelberg H., The theory of market economy, Oxford: Oxford University Press; 1952.
• Wollmer R., Removing Arcs from a Network, Operations Research, 12(6), 934-940, 1964.
• Israeli, E., Wood, R. K., Shortest-path network interdiction, Networks 40 (2), 97–111, 2002.
• Cappanera P., Scaparra M. P., Optimal allocation of protective resources in shortest-path networks, Transportation Science 45 (1), 64–80, 2011.
• Shimizu K., Ishizuka Y., Bard J. F., Nondifferentiable and two-level mathematical programming, Springer Science & Business Media, 2012.
• Wood R. K., Deterministic network interdiction, Mathematical and Computer Modelling 17 (2), 1–18,1993.
• Cormican K. J., Morton D. P., Wood R. K., Stochastic network interdiction, Operations Research 46 (2), 184–197, 1998.
• McMasters A. W., Mustin T. M., Optimal interdiction of a supply network, Naval Research Logistics Quarterly 17 (3), 261–268, 1970.
• Assimakopoulos N., A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (6), 413–422, 1987.
• Farley J. D., Breaking al qaeda cells: A mathematical analysis of counterterrorism operations (a guide for risk assessment and decision making), Studies in Conflict & Terrorism 26 (6), 399–411, 2003.
• Morton D. P., Pan F., Saeger K. J., Models for nuclear smuggling interdiction, IIE Transactions 39 (1), 3–14, 2007.
• Washburn, A., Wood, K., Two-person zero-sum games for network interdiction, Operations research 43 (2), 243–251, 1995.
• Ramamoorthy P., Jayaswal S., Sinha A., Vidyarthi N., Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods, Indian Institute Of Management Ahmedabad-380 015,
India, 2016.
• Aliakbarian N., vd., A bi-level programming model for protection of hierarchical facilities under imminent attacks, Computers & Operations Research 64 (2015) 210–224, 2015.
• Church RL, Scaparra MP, Middleton RS, Identifying critical infrastructure: the median and covering facility interdiction problems, Ann Assoc Am Geogr 94(3):491–502, 2004.
• Salmeron J., Wood K., Baldick R., Analysis of Electric Grid Security Under Terrorist Threat, IEEE Transactions On Power Systems, Vol. 19, NO. 2, 2004.
• Salmeron J., Wood K., The Value of Recovery Transformers in Protecting an Electric Transmission Grid Against Attack, IEEE Transactions On Power Systems, Vol. 30, NO. 5, 2015.
• Aksen D., Aras D., A bilevel fixed charge location model for facilities under imminent attack, Computers & Operations Research 39, 1364–1381, 2011.
• Losada C., Scaparra M.P., Church R.L., On a bi-level formulation to protect uncapacitated p-median systems with facility recovery time and frequent disruptions, Electronic Notes in Discrete Mathematics 36, 591–598, 2010.
• Losada C., Scaparra M.P., O’Hanley J.R., Optimizing system resilience: A facility protection model with recovery time, European Journal of Operational Research 217, 519–530, 2012-a.
• Aksen D., Akca S. Ş., Aras A., A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Computers & Operations Research 41, 346–358, 2014.
• Lezama J.M.L., Gomez J.C., Galeano N. M., Assessment of the Electric Grid Interdiction Problem using a nonlinear modeling approach, Electric Power Systems Research 144, 243–254, 2017.
• Wu X., Conejo A.J., An Efficient Tri-Level Optimization Model for Electric Grid Defense Planning, IEEE Transactions On Power Systems, Vol. 32, No. 4, 2017.
• Alguacil N., Delgadillo A., Arroyo J.M., A trilevel programming approach for electric grid defense planning, Computers & Operations Research 41, 282–290, 2014
• Jian G.J., Liu X., Sun L., Yin J., Optimal allocation of protective resources in urban rail transit networks against intentional attacks, Transportation Research Part E 84, 73–87, 2015.
• Ghaffarinasaba N., Atayi R., An implicit enumeration algorithm for the hub interdiction median problem with fortification, European Journal of Operational Research 267, 23–39, 2018.Losada C., Scaparra M.P.,
• Church R. L., Daskin M. S., The stochastic interdiction median problem with disruption intensity levels, Ann Oper Res, 201:345–365, 2012-b
• Aksen D., Akca S.Ş., Aras N., A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Computers & Operations Research 41, 346–358, 2014.
• Ramamoorthy P., Jayaswal S., Sinha A., Vidyarthi N., Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches”, European Journal of Operational Research, 1–16, 2018
• Aksen D., Piyade N., Aras N., The budget constrained r-interdiction median problem with capacity expansion, CEJOR, 18:269–291
DOI 10.1007/s10100-009-0110-6, 2010.
• Keçici S., Aras N., Verter V., Facility network design under the threat of terrorist attacks, Springer Verlag, Optim Lett, 6:1101–1121 DOI 10.1007/s11590-011-0412-1, 2012.
• Zhu Y., Zheng Z., Zhang X., Cai K., The r-interdiction median problem with probabilistic protection and its solution algorithm, Computers & Operations Research 40, 451–462, 2013.
• Liberatore F.,Scaparra M.P., Daskin M.S., Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification, Computers & Operations Research, 357–366, 2011.