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.
Citation
Operations Research 55, 662-673, 2007