optimization problems in which the random variables are represented by an extremely large number of scenarios. The method involves the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function (pdBf) representing the combination (F,p) of the binarized probability distribution F and the enforced probability level p. We show that the pdBf representing (F,p) can be compactly extended as a disjunctive normal form (DNF). The DNF is a collection of combinatorial p-patterns, each of which defining sufficient conditions for a probabilistic constraint to hold. We propose two linear programming formulations for the generation of p-patterns which can be subsequently used to derive a linear programming inner approximation of the original stochastic problem. A formulation allowing for the concurrent generation of a p-pattern and the solution of the deterministic equivalent of the stochastic problem is also proposed. Results show that large-scale stochastic problems, in which up to 50,000 scenarios are used to describe the stochastic variables, can be consistently solved to optimality within a few seconds.
To appear in Operations Research.
View Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems