Everyone who is interested is welcome to attend the lecture of Gustavo Angulo, entitled 'On a class of Stochastic Programs with Exponentially many Scenarios'.
Abstract:
In stochastic programming, it is usually assumed that the random data of
the problem follows a known distribution P. When P is either continuous or
finite with a large number of atoms, sampling methods can be used to
approximate the true problem with a model involving a reasonable number of
scenarios. But what happens when P is ``easy'' to describe and still
involves an enormous number of possible outcomes? A natural question to ask
is whether we can solve the true problem without relying on sampling.
In this work, we propose a model where scenarios are affinely parametrized
by the vertices or integral vectors within a given polytope Q. For
instance, with Q being the n-dimensional unit cube, a vertex is a binary
vector that might represent the availability of a set of resources in a
particular scenario. Given that in general the number of vertices is
exponential with respect to the size of the description of Q, a natural
integer programming formulation that includes binary variables to choose
which scenarios are satisfied is simply impractical. For this reason, we
present a formulation that implicitly discards the k worst scenarios for a
given vector x without including variables for each scenario, leading to a
mixed-binary program of moderate size. We also study a model where the
average cost of the k worst scenarios is considered, for which we present a
compact linear formulation. These models can be interpreted in the context
of VaR- and CVaR-constrained problems, respectively, exhibiting similar
relationships. A key tool we exploit is a dynamic program to optimize a
linear function over a set of integral matrices with lexicographically
ordered rows, which might be of independent interest.
This is joint work with Mathieu Van Vyve.
