Geodesic
A bilevel ``Attacker--Defender'' model to~choosing~the~composition of attack means
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 16-33.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a bilevel model of estimating the costs of the attacking party (the Attacker) for a successful attack of a given set of objects protected by the other party (the Defender). The Attacker and the Defender have multiple means to, correspondingly, attack and protect the objects, and the Attacker's costs depend on the Defender's means of protection. The model under consideration is based on the Stackelberg game, where the Attacker aims to successfully attack the objects with the least costs, while the Defender maximizes the Attacker's losses committing some limited budget. Formally, the “Attacker–Defender” model can be written as a bilevel mixed-integer program. The particularity of the problem is that the feasibility of the upper-level solution depends on all lower-level optimal solutions. To compute an optimal solution of the bilevel problem under study, we suggest some algorithm that splits the feasible region of the problem into subsets and reducing the problem to a sequence of bilevel subproblems. Specificity of feasible regions of these subproblems allows us to reduce them to common mixed-integer programming problems of two types. Bibliogr. 14.
Keywords: partition of the feasible region, bilevel subproblem, optimality condition. 
@article{DA_2019_26_4_a1,
     author = {V. L. Beresnev and A. A. Melnikov},
     title = {A bilevel {``Attacker--Defender''} model to~choosing~the~composition of attack means},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {16--33},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_4_a1/}
}
TY  - JOUR
AU  - V. L. Beresnev
AU  - A. A. Melnikov
TI  - A bilevel ``Attacker--Defender'' model to~choosing~the~composition of attack means
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 16
EP  - 33
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_4_a1/
LA  - ru
ID  - DA_2019_26_4_a1
ER  - 
%0 Journal Article
%A V. L. Beresnev
%A A. A. Melnikov
%T A bilevel ``Attacker--Defender'' model to~choosing~the~composition of attack means
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 16-33
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_4_a1/
%G ru
%F DA_2019_26_4_a1
V. L. Beresnev; A. A. Melnikov. A bilevel ``Attacker--Defender'' model to~choosing~the~composition of attack means. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 16-33. http://geodesic.mathdoc.fr/item/DA_2019_26_4_a1/

[1] T. Ding, L. Yao, F. Li, “A multi-uncertainty-set based two-stage robust optimization to Defender-Attacker-Defender model for power system protection”, Reliab. Eng. Syst. Saf., 169 (2018), 179–186 | DOI | MR

[2] N. Alguacil, A. Delgadillo, J. M. Arroyo, “A trilevel programming approach for electric grid defense planning”, Comput. Oper. Res., 41:1 (2014), 282–290 | DOI | MR | Zbl

[3] V. L. Beresnev, “Mathematical models for planning development of technical means systems”, Diskretn. Anal. Issled. Oper., Ser. 2, 4:1 (1997), 4–29 (Russian) | Zbl

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

[5] F. Liberatore, M. P. Scaparra, 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 | DOI | MR | Zbl

[6] S. Sadeghi, A. Seifi, E. Azizi, “Trilevel shortest path network interdiction with partial fortification”, Comput. Ind. Eng., 106 (2017), 400–411 | DOI

[7] H. Stackelberg, The theory of the market economy, Oxford Univ. Press, Oxford, 1952, 289 pp.

[8] S. Dempe, Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[9] M. Fischetti, I. Ljubic, M. Sinnl, “Benders decomposition without separability: A computational study for capacitated facility location problems”, Eur. J. Oper. Res., 253:3 (2016), 557–569 | DOI | MR | Zbl

[10] S. Martello, P. Toth, Knapsack problems: algorithms and computer implementations, John Wiley Sons, Inc., New York, 1990, 306 pp. | MR | Zbl

[11] H. Kellerer, U. Pferschy, D. Pisinger, Knapsack problems, Springer, Heidelberg, 2004, 546 pp. | MR | Zbl

[12] Y. A. Kochetov, A. V. Plyasunov, “Polynomially solvable class of linear bilevel programming problems”, Diskretn. Anal. Issled. Oper., Ser. 2, 4:2 (1997), 23–33 (Russian) | MR

[13] A. V. Plyasunov, “Linear bilevel programming problem with multivariant knapsack problem on the lower level”, Diskretn. Anal. Issled. Oper., Ser. 2, 10:1 (2003), 44–52 (Russian) | MR | Zbl

[14] J. T. Moore, J. F. Bard, “The mixed integer linear bilevel programming problem”, Oper. Res., 38:5 (1990), 911–921 | DOI | MR | Zbl