Date: June, 6th, 11h30
Place: ULB Bruxelles
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 hap- pens 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 for- mulation 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 mod- erate 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, respec- tively, 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.
