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

Öz

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.

Anahtar Kelimeler

• 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

Öz

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.

Anahtar Kelimeler

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

Kaynakça

1. 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.
2. Stackelberg H., The theory of market economy, Oxford: Oxford University Press; 1952.
3. Wollmer R., Removing Arcs from a Network, Operations Research, 12(6), 934-940, 1964.
4. Israeli, E., Wood, R. K., Shortest-path network interdiction, Networks 40 (2), 97–111, 2002.
5. Cappanera P., Scaparra M. P., Optimal allocation of protective resources in shortest-path networks, Transportation Science 45 (1), 64–80, 2011.
6. Shimizu K., Ishizuka Y., Bard J. F., Nondifferentiable and two-level mathematical programming, Springer Science & Business Media, 2012.
7. Wood R. K., Deterministic network interdiction, Mathematical and Computer Modelling 17 (2), 1–18,1993.
8. Cormican K. J., Morton D. P., Wood R. K., Stochastic network interdiction, Operations Research 46 (2), 184–197, 1998.

9. McMasters A. W., Mustin T. M., Optimal interdiction of a supply network, Naval Research Logistics Quarterly 17 (3), 261–268, 1970.
10. Assimakopoulos N., A network interdiction model for hospital infection control, Computers in Biology and Medicine 17 (6), 413–422, 1987.
11. 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.
12. Morton D. P., Pan F., Saeger K. J., Models for nuclear smuggling interdiction, IIE Transactions 39 (1), 3–14, 2007.
13. Washburn, A., Wood, K., Two-person zero-sum games for network interdiction, Operations research 43 (2), 243–251, 1995.
14. 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.
15. Aliakbarian N., vd., A bi-level programming model for protection of hierarchical facilities under imminent attacks, Computers & Operations Research 64 (2015) 210–224, 2015.
16. 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.
17. Salmeron J., Wood K., Baldick R., Analysis of Electric Grid Security Under Terrorist Threat, IEEE Transactions On Power Systems, Vol. 19, NO. 2, 2004.
18. 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.
19. Aksen D., Aras D., A bilevel fixed charge location model for facilities under imminent attack, Computers & Operations Research 39, 1364–1381, 2011.
20. 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.
21. 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.
22. Aksen D., Akca S. Ş., Aras A., A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Computers & Operations Research 41, 346–358, 2014.
23. 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.
24. 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.
25. Alguacil N., Delgadillo A., Arroyo J.M., A trilevel programming approach for electric grid defense planning, Computers & Operations Research 41, 282–290, 2014
26. 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.
27. 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.,
28. Church R. L., Daskin M. S., The stochastic interdiction median problem with disruption intensity levels, Ann Oper Res, 201:345–365, 2012-b
29. Aksen D., Akca S.Ş., Aras N., A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Computers & Operations Research 41, 346–358, 2014.
30. 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
31. 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.
32. 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.
33. 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.
34. 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.