.png){kind=icon}
返回
An exact method for binary fortification games
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2022.10.038.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A fortification game (FG) is a three-level, two-player hierarchical game, also known as defender-attacker -defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while at the innermost level the defender solves a recourse problem over the surviving or partially damaged assets. Fortification games have applications in various important areas, such as military operations, design of survivable networks, protection of facilities or power grid protection. In this work, we present an exact solution algorithm for FGs, in which the recourse problems correspond to (possibly NP-hard) combinatorial optimization prob-lems. The algorithm is based on a new generic mixed-integer linear programming reformulation in the natural space of fortification variables. Our new model makes use of fortification cuts that measure the contribution of a given fortification strategy to the objective function value. These cuts are generated when needed by solving separation problems, which correspond to (modified) middle-level interdiction games. We design a branch-and-cut-based solution algorithm based on fortification cuts, their strength-ened versions and other speed-up techniques. We present a computational study using the knapsack for-tification game and the shortest path fortification game. For the latter one, we include a comparison with a state-of-the-art solution method from the literature. Our algorithm outperforms this method and allows us to solve previously unsolved instances with up to 330 386 nodes and 1 202 458 arcs to optimality.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
Keyword:
Combinatorial optimization
Three-level optimization
Branch-and-cut
Shortest path fortification
Maximum knapsack fortification
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
分享收藏A tri-level optimization model to mitigate coordinated attacks on electric power systems in a cyber-physical environment网络物理环境下缓解电力系统协同攻击的三层优化模型.png)
APPLIED ENERGYOAAI
APPLIED ENERGYIF11
OAAI分享收藏分享收藏
查看更多内容