Том 27, номер 3, 2020 г., Стр. 5-27

УДК 519.8+518.25
Береснев В. Л., Мельников А. А.
Планирование защиты, минимизирующей дефицит ресурса в худшем сценарии разрушения сети снабжения

Аннотация:
Рассматривается модель планирования защиты рёбер сети снабжения некоторым ресурсом. В вершинах сети располагаются потребители и поставщики ресурса, а рёбра сети позволяют мгновенно и в неограниченном количестве перемещать ресурс между вершинами. Защищающая сторона располагает ограниченным бюджетом. Она стремится определить множество рёбер, защиту которых позволяет обеспечить бюджет, таким образом, чтобы минимизировать ущерб от выхода из строя части незащищённых рёбер. В качестве меры ущерба используется суммарный объём дефицита ресурса, возникающий в худшем сценарии разрушения сети. Задача защищающейся стороны таким образом представляет собой задачу семейства «защитник — атакующий», формализуемую в виде минимаксной смешанно-целочисленной задачи математического программирования. Для отыскания оптимального решения защищающейся стороны предложено две схемы генерации отсечений, опирающихся на переформулировку задачи в виде задачи смешанно-целочисленного математического программирования с экспоненциальным числом ограничений.
Табл. 2, ил. 4, библиогр. 13.

Ключевые слова: задача «защитник — атакующий», суммарный дефицит, генерация отсечений.

DOI: 10.33048/daio.2020.27.687

Береснев Владимир Леонидович ^1,2
Мельников Андрей Андреевич ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru, melnikov@math.nsc.ru

Статья поступила 9 мая 2020 г.
После доработки — 22 мая 2020 г.
Принята к публикации 25 мая 2020 г.

Литература

[1] Grötschel M., Monma C. L., Stoer M. Design of survivable networks // Handb. Oper. Res. Manage. Sci. 1995. Vol. 7. P. 617–672.

[2] Callaway D. S., Newman M. E. J., Strogatz S. H., Watts D. J. Network robustness and fragility: Percolation on random graphs // Phys. Rev. Lett. 2000. Vol. 85. P. 5468–5471.

[3] Nagurney A., Qiang Q. Fragile networks: Identifying vulnerabilities and synergies in an uncertain world // Int. Trans. Oper. Res. 2009. Vol. 19, No. 1–2. P. 123–160.

[4] Brown G., Carlyle M., Salmerón J., Wood K. Defending critical infrastructure // Interfaces. 2006. Vol. 36, No. 6. P. 530–544.

[5] Scaparra M. P., Church R. L. A bilevel mixed-integer program for critical infrastructure protection planning // Comput. Oper. Res. 2008. Vol. 35. P. 1905–1923.

[6] Golden B. A problem in network interdiction // Naval Res. Logist. Q. 1978. Vol. 25, No. 4. P. 711–713.

[7] Wood R. K. Deterministic network interdiction // Math. Comput. Model. 1993. Vol. 17, No. 2. P. 1–18.

[8] Sadeghi S., Seifi A., Azizi E. Trilevel shortest path network interdiction with partial fortification // Comput. Ind. Eng. 2017. Vol. 106. P. 400–411.

[9] Dong L., Xu-chen L., Xiang-tao Y., Fei W. A model for allocating protection resources in military logistics distribution system based on maximal covering problem // 2010 Int. Conf. Logist. Syst. Intell. Manage. (Harbin, China, Jan. 9–10, 2010). Vol. 1. 2010. P. 98–101.

[10] Alekseeva E. V., Kochetov Yu. A. Metaheuristics and exact methods for the discrete ($r|p$)–centroid problem // Metaheuristics for bi-level optimization. Berlin: Springer, 2013. P. 189–219. (Stud. Comput. Intell.; Vol. 482).

[11] Roboredo M. C., Aizemberg L., Pessoa A. A. An exact approach for the $r$-interdiction covering problem with fortification // Cent. Eur. J. Oper. Res. 2019. Vol. 27. P. 111–131.

[12] Roboredo M. C., Pessoa A. A. A branch-and-cut algorithm for the discrete ($r|p$)-centroid problem // Eur. J. Oper. Res. 2013. Vol. 224, No. 1. P. 101–109.

[13] Gurobi optimizer reference manual. Gurobi Optimization, 2020. Available at
http://www.gurobi.com/documentation/9.0/refman/index.html (accessed May 25, 2020).