Survivable network design under optimal and heuristic interdiction scenarios
Survivable network design under optimal and heuristic interdiction scenarios
复制标题
最优和启发式拦截场景下的可生存网络设计
DOI：
10.1007/s10898-006-9067-3
复制
发表时间：
2007
影响因子：
1.8
通讯作者：
Fransisca Sudargho
中科院分区：
文献类型：
--
作者：
J. Smith;Churlzu Lim;Fransisca Sudargho
我们研究了在各种情况下建立或加固网络以抵御敌人攻击的问题。特别是，我们研究的情况下，敌人可以摧毁任何弧的设计师在网络上构建的任何部分，受到一些阻断预算。这个问题采取了一个三层两人游戏的形式，在这个游戏中，设计者首先构建一个网络，并通过网络传输一组初始流。敌人接下来采取行动，摧毁设计者网络中的一组构造弧，而设计者最后采取行动，在网络中传输最后一组流。这种性质的大多数研究都假设敌人会采取最佳行动;然而，在现实世界中，我们不一定能假设敌人是理性的。因此，我们规定最佳的网络设计算法为三种不同的配置文件的敌人的行动：敌人破坏弧的基础上的能力，根据初始流量，或采取最佳行动，以尽量减少我们的最大利润从传输流。
We examine the problem of building or fortifying a network to defend against enemy attacks in various scenarios. In particular, we examine the case in which an enemy can destroy any portion of any arc that a designer constructs on the network, subject to some interdiction budget. This problem takes the form of a three-level, two-player game, in which the designer acts first to construct a network and transmit an initial set of flows through the network. The enemy acts next to destroy a set of constructed arcs in the designer’s network, and the designer acts last to transmit a final set of flows in the network. Most studies of this nature assume that the enemy will act optimally; however, in real-world scenarios one cannot necessarily assume rationality on the part of the enemy. Hence, we prescribe optimal network design algorithms for three different profiles of enemy action: an enemy destroying arcs based on capacities, based on initial flows, or acting optimally to minimize our maximum profits obtained from transmitting flows.