Robust and Adaptive Network Flows
Robust and Adaptive Network Flows
复制标题
稳健且自适应的网络流
DOI：
10.1287/opre.2013.1200
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
S. Stiller
中科院分区：
文献类型：
--
作者：
D. Bertsimas;E. Nasrabadi;S. Stiller
本文从鲁棒优化的角度研究了不确定环境下的网络流问题。与以前的工作相比，我们考虑的情况下，网络参数（例如，容量）是已知的和确定的，但是网络结构（例如，节点和弧）存在不确定性。在本文中，我们研究了鲁棒和自适应版本的最大流问题和最小割问题的网络节点和弧故障，并建立结构和计算结果。自适应两阶段模型在网络中出现故障后对解进行调整。这导致了一个更灵活的模型，并产生更少的保守性的解决方案相比，鲁棒model.We表明，鲁棒最大流问题可以在多项式时间内解决，但鲁棒最小割问题是NP-难的。我们还证明了自适应版本是NP难的。我们进一步描述的自适应模型作为一个两个人的零和博弈，并证明了在这样的games. Therefore，我们认为一个基于路径的制定相比，更常用的弧为基础的版本的流量的流量。这导致了一个不同的模型的鲁棒性最大流量。我们分析这个问题，以及开发一个简单的线性优化模型，以获得近似的解决方案。此外，我们引入了自适应最大流的概念，随着时间的推移，在网络上的弧上的渡越时间。与确定性的情况下，我们表明，这个问题是NP-困难的串-并联图，即使是只允许一个弧失败的情况下。最后，我们提出了基于线性优化模型，表现出强大的计算性能的大规模的实例。
We study network flow problems in an uncertain environment from the viewpoint of robust optimization. In contrast to previous work, we consider the case that the network parameters (e.g., capacities) are known and deterministic, but the network structure (e.g., nodes and arcs) is subject to uncertainty. In this paper, we study the robust and adaptive versions of the maximum flow problem and minimum cut problems in networks with node and arc failures, and establish structural and computational results. The adaptive two-stage model adjusts the solution after the realization of the failures in the network. This leads to a more flexible model and yields less conservative solutions compared to the robust model.We show that the robust maximum flow problem can be solved in polynomial time, but the robust minimum cut problem is NP-hard. We also prove that the adaptive versions are NP-hard. We further characterize the adaptive model as a two-person zero-sum game and prove the existence of an equilibrium in such games.Moreover, we consider a path-based formulation of flows in contrast to the more commonly used arc-based version of flows. This leads to a different model of robustness for maximum flows. We analyze this problem as well and develop a simple linear optimization model to obtain approximate solutions. Furthermore, we introduce the concept of adaptive maximum flows over time in networks with transit times on the arcs. Unlike the deterministic case, we show that this problem is NP-hard on series-parallel graphs even for the case that only one arc is allowed to fail. Finally, we propose heuristics based on linear optimization models that exhibit strong computational performance for large-scale instances.