On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions

The paper studies large scale mixed integer reformulation approach to stochastic programming problems containing probability and quantile functions, under assumption of discreteness of the probability distribution involved. Jointly with general sample approximation technique and contemporary mixed integer programming solvers the approach gives a regular framework to solution of practical probabilistic programming problems. In the literature this approach is applied basically to chance constrained problems with discrete probability distribution. In the present paper we extend it to more complicated problems, containing several probability/quantile functions both in the objective and constraints; in particular we consider probability and quantile functions optimization problems. First we show that the approach is applicable to probabilistic programming problems with objective and constraint functions monotonically depending on several probability functions. Next we remark that the general framework is applicable to optimization problems containing quantile functions, provided the last are uniformly bounded from below. As a solution technique beside general solvers we specialize branch and bound method for optimization of the probability function. To speed up the branch and bound method we derive dominance between integral variables basing on the dominance between probabilistic scenarios. Finally we note that some of probability functions may be defined on different probability spaces, this allows to treat within the considered framework some ambiguous probabilistic problems with uncertain probability distributions. As illustrations of the general framework we consider applications to (robust) safety first portfolio selection and quantile optimization.

Citation

V.M.Glushkov Institute of Cybernetics, Glushkov avenue 40, 03178, Kiev, Ukraine; 17 May, 2010

Article

Download

View On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions