Abstract.
We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002
Key words. stochastic programming – integer programming – valid inequalities
Rights and permissions
About this article
Cite this article
Ruszczyński, A. Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program., Ser. A 93, 195–215 (2002). https://doi.org/10.1007/s10107-002-0337-7
Issue Date:
DOI: https://doi.org/10.1007/s10107-002-0337-7