Risk-Averse Stochastic Optimization: Models and Algorithms
Chaitanya Swamy
University of Waterloo, Department of Combinatorics and Optimization
Abstract:
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.