Risk-Averse Stochastic Optimization: Models and Algorithms



Chaitanya Swamy
University of Waterloo, Department of Combinatorics and Optimization

Monday  September 15, 2008
4:00 PM, 5130 Upson Hall



We consider various stochastic models that incorporate the notion of risk-averseness into the standard 2-stage recourse model, and develop techniques for solving the algorithmic problems arising in these models. A key notable feature of our work that distinguishes it from work in some other related models, is that we obtain results in the black-box setting, that is, where one is given only sampling access to the underlying distribution. In the standard 2-stage model, one is given a probability distribution over possible realizations of the data, and one seeks to take actions both before and after the data has been realized so as to minimize the expected cost incurred. We consider a model, that we call the risk-averse budget model, which incorporates the notion of risk-averseness via a probabilistic constraint that restricts the probability (according to the underlying distribution) of the second-stage cost exceeding a given budget B to at most a given input threshold ρ, thus, in some sense, guarding against "disaster scenarios". We also a consider a closely-related model that we call the risk-averse robust model, where we seek to minimize the first-stage cost and the (1-ρ)-quantile of the second-stage cost.

We obtain approximation algorithms for a variety of combinatorial optimization problems including the set cover, vertex cover, multicut on trees, min cut, and facility location problems, in our risk-averse models with black-box distributions. We first devise a fully polynomial approximation scheme for solving the LP-relaxations of a variety of risk-averse budgeted problems. Complementing this, we give a rounding procedure that lets us use existing LP-based approximation algorithms for the 2-stage stochastic and/or deterministic counterpart of the problem to round the fractional solution. Thus, we obtain near-optimal solutions to risk-averse problems that preserve the budget approximately and incur a small blow-up of the probability threshold (both of which are unavoidable). To the best of our knowledge, these are the first approximation results for problems involving probabilistic constraints with black-box distributions.