Robust and Adaptive Network Flows

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Nasrabadi, Ebrahim; Stiller, Sebastian
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Technical University of Berlin
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1200
• 发表日期: 2013
• 页码: 1218-1242
• 关键词: Optimization; algorithms; hardness

摘要

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 twoperson 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.