Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems

Miguel Lejeune

Operations Research, 2012, vol. 60, issue 6, 1356-1372

Abstract: We propose a new modeling and solution method for probabilistically constrained optimization problems. The methodology is based on the integration of the stochastic programming and combinatorial pattern recognition fields. It permits the fast solution of stochastic 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 defining sufficient conditions for a probabilistic constraint to hold. We propose two linear programming formulations for the generation of p -patterns that 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. The number of binary variables included in the deterministic equivalent formulation is not an increasing function of the number of scenarios used to represent uncertainty. 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.

Keywords: programming; stochastic; probability; combinatorial pattern; probabilistic constraint; Boolean programming (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1120 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:6:p:1356-1372

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().