Robust and Adaptive Network Flows

Dimitris Bertsimas (), Ebrahim Nasrabadi () and Sebastian Stiller ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Ebrahim Nasrabadi: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Sebastian Stiller: Institut für Mathematik, Technische Universität Berlin, 10623 Berlin, Germany

Operations Research, 2013, vol. 61, issue 5, 1218-1242

Abstract: 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.

Keywords: network flows; robust optimization; game theory; flows over time (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1200 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:5:p:1218-1242

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().