Linear programming with stochasticity?

Question

Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution.

Now, I would like to solve the same problem but with stochasticity reintroduced based on the probability distributions.

Can this still be solved using LP techniques?

If not, what are the natural alternatives?

• Brian Borchers: How are your coefficients distributed? Some discrete distribution? Normal? Uniform? In what sense do you want the constraint to be satisfied? In expected value (on average)? with specified high probability?

Answer 1

There is a huge literature on "stochastic programming", but you're probably interested in what is called "chance constrained programming", in which the constraint coefficients are random variables, and you want to find a solution $x$ such that each constraint is individually satisfied with probability $\eta$ ($\eta$ might 0.95, 0.99, etc.)

These problems cannot typically be reformulated as LP's, but they can sometimes be formulated and solved as other types of optimization problems. For example, if the constraint coefficients of your LP have a multivariate normal distribution, then the chance constrained version of the LP can be formulated and solved as a second order cone program. You can find a discussion of this in section 4.4 of Convex Optimization by Boyd and Vandenberghe.

You should also look up the broader topic of "Robust Optimization" for methods that work with various kinds of uncertain coefficients.