Stochastic linear optimization approaches for joint probabilistic constrained problems with integer random variables
The Stochastic Programming field combines optimization and probability theory. The focus of this field is dealing with optimization problems with uncertainty, in part or in all data, which arises naturally in real problems. There are several ways to model uncertainty and we describe some of them in this dissertation. Among these possibilities, we focus on stochastic linear optimization problems with joint probabilistic constraints in which we can separate the stochastic part from the deterministic part. Considering this type of constraint, we approach the case in which the probability distribution functions are integer. We present the concept of p-Level Efficient Points (p-LEPs) and we show examples in which the convex hull of the p-LEPs may contain unwanted points. Later on, we provide properties and geometric aspects of the convex hull of the p-LEPs and the notion of α-concavity for integer probability distribution functions. We include an algorithm to enumerate the p-LEPs and we exemplify its application to the stochastic set cover problem. Afterwards, we reformulate the stochastic problem with joint probabilistic constraints transforming them into deterministic problems using the p-LEPs. We present five approaches to solve these reformulations, they are: disjunctive programming, convex relaxation, cutting planes algorithm, column generation algorithm and the combination of the last two techniques. We use each one of these approaches to solve several instances of the stochastic set cover problem, in which we vary the number of dimensions and also the probability distribution functions.