Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra (Q1396210)

Stochastic programming problems are considered assuming that constraints are defined as inequalities involving probabilities related to the random variables with discrete distributions. The number of finitely many realizations of the random variables, called scenarios, is an important parameter defining the complexity of a problem. The original stochastic programming problem is reduced to a large scale mixed integer programming (MIP) problem with knapsack constraints. A special cut and branch method is developed based on introducing and lifting new valid inequalities for the probabilities of events in a cover. The developed method is applied to two versions of an example problem: with 100 and 200 scenarios. The latter problem is reduced to a MIP with 28000 continuous variables, 200 binary variables, and 2001 constraints. The problem appeared too difficult for a standard MIP solver CPLEX, but it was successfully solved by the developed method.