Two-Stage Robust Network Flow and Design under Demand Uncertainty

Alper Atamturk (atamturkieor.berkeley.edu)
Muhong Zhang (mhzhangieor.berkeley.edu)

Abstract: We describe a two-stage robust optimization approach for solving network flow and design problems with demand uncertainty. We give an explicit characterization of the first-stage decisions and prove that the corresponding separation problem is NP-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. By using a ``budget of uncertainty'' for demand we give an upper bound on the probability of infeasibility of the robust solution for a random demand vector. We generalize the approach to multi-commodity flow and design. We give applications to production lot-sizing and facility location problems and present computational experiments comparing two-stage robust optimization with single-stage robust optimization and scenario-based two-stage stochastic optimization.

Keywords:

Category 1: Robust Optimization

Category 2: Network Optimization

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Operations Research 55, 662-673, 2007

Download:

Entry Submitted: 02/23/2005
Entry Accepted: 02/23/2005
Entry Last Modified: 04/15/2008

Modify/Update this entry