Polynomial-time identification of robust network flows under uncertain arc failures
Polynomial-time identification of robust network flows under uncertain arc failures
复制标题
DOI：
10.1007/s11590-009-0125-x
复制
发表时间：
2009-05
影响因子：
1.6
通讯作者：
V. Boginski;C. Commander;T. Turko
中科院分区：
文献类型：
--
作者：
V. Boginski;C. Commander;T. Turko
我们提出了线性规划（LP）为基础的解决方案的网络流问题的多个不确定的电弧故障，它允许在多项式时间在一定条件下找到强大的最优解。我们证明了这一事实，证明考虑的一类问题下的不确定性与线性损失函数，在相应的LP配方中的实体的数量是多项式的弧在网络中的数量。所提出的配方是有效的稀疏网络，以及时间关键的网络系统，快速和强大的决策发挥了至关重要的作用。
We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures, which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role.