Optimization Online


Two-Stage Robust Network Flow and Design under Demand Uncertainty

Alper Atamturk (atamturk***at***ieor.berkeley.edu)
Muhong Zhang (mhzhang***at***ieor.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.


Category 1: Robust Optimization

Category 2: Network Optimization

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Operations Research 55, 662-673, 2007


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society