Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization

Abstract

Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) the input is specified by a probability distribution. We consider the well-studied paradigm of stochastic recourse models, where the uncertainty evolves through a series of stages and one can take decisions in each stage in response to the new information learned. We obtain the first approximation algorithms for a variety of 2-stage and k-stage stochastic integer optimization problems where the underlying random data is given by a "black box" and no restrictions are placed on the costs of the two stages: one can merely sample data from this distribution, but no direct information about the distributions is given. Our results are based on two principal components. First, we show that for a broad class of 2-stage and k-stage linear programs, where k is not part of the input, given only a "black box" to draw independent samples from the distribution, one can, for any \epsilon>0, compute a solution of cost guaranteed to be within a (1+\epsilon) factor of the optimum, in time polynomial in 1/\epsilon, the size of the input, and a parameter \lambda that is the ratio of the cost of the same action in successive stages which is a lower bound on the sample complexity in the "black-box" model. This is based on reformulating the stochastic linear program, which has both an exponential number of variables and an exponential number of constraints, as a compact convex program, and adapting tools from convex optimization to solve the resulting program to near optimality. In doing so, a significant difficulty that we must overcome is that even evaluating the objective function of this convex program at a given point may be quite difficult and provably hard. To the best of our knowledge, this is the first such result for multi-stage stochastic programs. Second, we give a rounding approach for stochastic integer programs that shows that approximation algorithms for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Thus we obtain approximation algorithms for several stochastic problems, including the stochastic versions of the set cover, vertex cover, facility location, multicut (on trees) and multicommodity flow problems.