Том 25, номер 3, 2018 г., Стр. 5-22

УДК 519.8
Береснев В. Л., Давыдов И. А., Кононова П. А., Мельников А. А.
Двухуровневая модель «защитник—атакующий» при альтернативных сценариях атаки

Аннотация:
Рассматривается двухуровневая модель «защитник — атакующий», построенная на основе игры Штакельберга. Задано множество объектов, оказывающих социально значимые услуги для известного множества потребителей и являющихся потенциальными целями для возможной атаки. Защитнику (Лидеру) не известен сценарий атаки и приоритеты атакующего (Последователя) по выбору объектов для атаки, однако Лидер может рассмотреть несколько возможных сценариев, покрывающих планы Последователя. Задача Лидера в такой ситуации состоит в том, чтобы, исходя из возможных сценариев атаки, выбрать такие объекты для защиты, что при условии рационального решения Последователя о выборе целей атаки суммарные затраты на защиту объектов и ликвидацию последствий атаки будут наименьшими. Формально предлагаемая модель представляет собой задачу двухуровневого смешанно-целочисленного программирования, включающую задачу верхнего уровня (задачу Лидера) и нижнего уровня (задачу Последователя). Основные усилия в работе направлены на переформулировку данной задачи в виде одноуровневых задач математического программирования. Такие задачи строятся с использованием свойств оптимального решения задачи Последователя, позволяющих сформулировать необходимые и достаточные условия оптимальности в виде линейных соотношений.
Библиогр. 16.

Ключевые слова: двухуровневое программирование, условия дополняющей нежёсткости, критерий оптимальности.

DOI: 10.17377/daio.2018.25.612

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

Статья поступила 19 марта 2018 г

Литература

[1] Давыдов И. А., Мельников А. А., Кононова П. А. Локальный поиск для задач балансировки нагрузки серверов большой размерности // Автоматика и телемеханика. 2017. № 3. С. 34–50.

[2] Aksen D., Aras N. A bilevel fixed charge location model for facilities under imminent attack // Comput. Oper. Res. 2012. Vol. 39, No. 1. P. 1364–1381.

[3] Aksen D., Piyade N., Aras N. The budget constrained r-interdiction median problem with capacity expansion // Central Eur. J. Oper. Res. 2010. Vol. 18, No. 3. P. 269–291.

[4] An B., Ordóñez F., Tambe M., Shieh E., Yang R., Baldwin C., DiRenzo J., Moretti K., Maule B., Meyer G. A deployed quantal response-based patrol planning system for the U. S. Coast Guard // Interfaces.
2013. Vol. 43, No. 5. P. 400–420.

[5] Angelo J. S., Barbosa H. J. C. A study on the use of heuristics to solve a bilevel programming problem // Int. Trans. Oper. Res. 2015. Vol. 22. P. 861–882.

[6] Beresnev V., Melnikov A. Facility location in unfair competition // Discrete Optimization and Operations Research. Proc. 9th Int. Conf., (Vladivostok, Russia, Sept. 19–23, 2016). Cham: Springer, 2016. P. 325–335. (Lect. Notes Comput. Sci.; Vol. 9869).

[7] Brotcorne L., Hanafi S., Mansi R. One-level reformulation of the bilevel knapsack problem using dynamic programming // Discrete Optimization 2013. Vol. 10, No. 1. P. 1–10.

[8] Delle Fave F. M., Jiang A. X., Yin Z., Zhang C., Tambe M., Kraus S., Sullivan J. P. Game-theoretic security patrolling with dynamic execution uncertainty and a case study on a real transit system // J. Artif. Intell. Res. 2014. Vol. 50. P. 321–367.

[9] Dempe S. Foundations of bilevel programming. Dordrecht: Kluwer Acad. Publ., 2002. 332 p.

[10] Jain M., Tsai J., Pita J., Kiekintveld C., Rathi S., Tambe M., Ordóñez F. Software assistants for randomized patrol planning for the LAX airport police and the federal air marshal service // Interfaces. 2010. Vol. 40, No. 4. P. 267–290.

[11] Jiang A. X., Yin Z., Zhang C., Tambe M., Kraus S. Game-theoretic randomization for security patrolling with dynamic execution uncertainty // Proc. 12th Int. Conf. Auton. Agents Multiagent Syst. (Saint Paul, MN, USA, May 6–10, 2013). Richland, SC: Int. Found. Auton. Agents Multiagent Syst., 2013. P. 207–214.

[12] Martello S., Toth P. Knapsack problems: Algorithms and computer implementations. New York: John Wiley & Sons, 1990.

[13] Melo M. T., Nickel S., Saldanha-Da-Gama F. A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon // Int. J. Production Econ. 2012. Vol. 136, No. 1. P. 218–230.

[14] 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.

[15] Stackelberg H. The theory of the market economy. Oxford: Oxf. Univ. Press, 1952. 289 p.

[16] Zhu Y., Zheng Z., Zhang X., Cai K. Y. The $r$-interdiction median problem with probabilistic protection and its solution algorithm // Comput. Oper. Res. 2013. Vol. 40. P. 451–462.