Optimization Online


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

Vladimir Norkin(norkin***at***i.com.ua)

Abstract: 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.

Keywords: stochastic programming, probabilistic programming, probability function, quantile function, mixed integer programming, branch and bound method

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

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

Download: [PDF]

Entry Submitted: 05/17/2010
Entry Accepted: 05/17/2010
Entry Last Modified: 05/17/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society