Optimization Online


Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix

Alexander Kogan (kogan***at***rutgers.edu)
Miguel Lejeune (mlejeune***at***gwu.edu)

Abstract: We develop a new modeling and exact solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sucient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations equivalent to the studied stochastic problem. We derive a set of strengthening valid inequalities for the reformulated problems. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the MIP reformulations are orders of magnitude faster to solve than the MINLP formulation. The method integrating the derived valid inequalities in a branch-and-bound algorithm has the best performance.

Keywords: Stochastic Programming, Boolean Function, Joint Probabilistic Constraint, Random Technology Matrix, Minorant, Threshold Function

Category 1: Stochastic Programming

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

Category 3: Applications -- Science and Engineering (Data-Mining )

Citation: Accepted for publication Mathematical Programming.


Entry Submitted: 09/14/2012
Entry Accepted: 09/14/2012
Entry Last Modified: 10/29/2013

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 Optimization Society