3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brian Borchers May 22 '17 at 0:22
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.