The OR-Notes by J E Beasley states:

Hence the problem:

minimise     5x+6y
subject to:
             Prob(a1x + a2y >= 3) >= 1-alpha
             x,y >= 0

is a well-defined problem.

This particular problem (because it contains just two variables) can be easily solved by a simple numeric search procedure. For example for alpha=0.01 the solution is x=3, y=0 and for alpha=0.05 the solution is x=1, y=1.

The feasible region for alpha=0.05 is shown below.

Feasible region for alpha=0.05

Here it is claimed that the example can be easily solved by a simple numeric search procedure. Does this mean that simplex solvers would be able to accept constraints such as the below

$$ \operatorname{Prob}(a_1x + a_2y >=3) \geq 0.95 $$

either directly or with some reformulation?

  • 3
    $\begingroup$ The Simplex Algorithm isn't a mindreader. As stated, the problem is NOT well-defined. What is the joint probability distribution of $a_1$ and $a_2$? Or in some manner, provide sufficient information so that the probability can be evaluated for any $x, y \ge 0$. $\endgroup$ Commented Sep 1, 2023 at 18:51
  • $\begingroup$ But the quote claims that it IS a well-defined problem. $\endgroup$
    – jbuddy_13
    Commented Sep 1, 2023 at 19:42
  • 1
    $\begingroup$ @jbuddy_13, the mentioned constraint is the chance constraint and also as Mark pointed out it is not well know at all. Just search OR community by "chance constraint" and see how is it possible to convert that into a solvable constraint that Simplex or other methods can deal with it. $\endgroup$
    – A.Omidi
    Commented Sep 1, 2023 at 20:02
  • 2
    $\begingroup$ @buddy_13 You left out this "part" of the quote: a1=i (i=1,...,6) with probability 1/6 a2=j (j=1,...,6) with probability 1/6 and further (implicitly assumed, but not stated on the webpage) the critically important assumption that a1 and a2 are independent of each other. Then you have a well-defined chance constraint and optimization problem. $\endgroup$ Commented Sep 2, 2023 at 10:35
  • $\begingroup$ I’m gathering that the assumption of independence is critical. I read recently that I’m situations where independence cannot be ensured, a1 and b1 can be sampled from, then constrain that across all samples, 95% of which >= 3. However this induces a MILP problem, which is much slower. $\endgroup$
    – jbuddy_13
    Commented Sep 2, 2023 at 14:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.