Two-Stage Robust Network Flow and Design Under Demand Uncertainty

Alper Atamtürk () and Muhong Zhang ()
Additional contact information
Alper Atamtürk: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720
Muhong Zhang: Department of Industrial Engineering and Operations Research, University of California, Berkeley, California 94720

Operations Research, 2007, vol. 55, issue 4, 662-673

Abstract: We describe a two-stage robust optimization approach for solving network flow and design problems with uncertain demand. In two-stage network optimization, one defers a subset of the flow decisions until after the realization of the uncertain demand. Availability of such a recourse action allows one to come up with less conservative solutions compared to single-stage optimization. However, this advantage often comes at a price: two-stage optimization is, in general, significantly harder than single-stage optimization.For network flow and design under demand uncertainty, we give a characterization of the first-stage robust decisions with an exponential number of constraints and prove that the corresponding separation problem is (N-script)(P-script)-hard even for a network flow problem on a bipartite graph. We show, however, that if the second-stage network topology is totally ordered or an arborescence, then the separation problem is tractable.Unlike single-stage robust optimization under demand uncertainty, two-stage robust optimization allows one to control conservatism of the solutions by means of an allowed “budget for demand uncertainty.” Using a budget of uncertainty, we provide an upper bound on the probability of infeasibility of a robust solution for a random demand vector.We generalize the approach to multicommodity network flow and design, and give applications to lot-sizing and location-transportation problems. By projecting out second-stage flow variables, we define an upper bounding problem for the two-stage min-max-min optimization problem. Finally, we present computational results comparing the proposed two-stage robust optimization approach with single-stage robust optimization as well as scenario-based two-stage stochastic optimization.

Keywords: network/graphs; applications; programming; integer (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (83)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0428 (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:55:y:2007:i:4:p:662-673

Access Statistics for this article

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