OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

Stochastic programming conversions

Recall the problem we had before:

minimise 5x+6y subject to: Prob(a_{1}x + a_{2}y >= 3) >=1-alphax,y >= 0

This problem is an example of a *stochastic (linear) program with
probabilistic constraints*. Such problems are also sometimes called
*chance-constrained linear programs*.

Solving SP's with probabilistic constraints

To solve SP's with probabilistic constraints we transform them into an equivalent deterministic program. Note here however, that as will become apparent below, even if the original SP is linear, the equivalent deterministic program may not be.

To illustrate how this can be done consider our simple example. Define
zero-one variables z_{ij} using:

z_{ij }= 1 if when a_{1}takes the value i (i=1,...,6) and a_{2}takes the value j (j=1,...,6) ix+jy>=3 = 0 otherwise

Let p_{ij} represent the probability that a_{1} takes
the value i (i=1,...,6) and a_{2} takes the j (j=1,...,6). Obviously
p_{ij}=1/36 in our simple example but we will leave it as a symbol
to illustrate the point.

Then for our SP:

minimise 5x+6y subject to: Prob(a_{1}x + a_{2}y >= 3) >=1-alphax,y >= 0

the deterministic equivalent is:

minimise Mz_{ij}+ (5x+6y) (1) subject to: z_{ij}>= [(ix+jy)-3+delta]/M i=1,... ,6 j=1,... ,6 (2) SUM[i=1,...,6] SUM[j=1,...,6] p_{ij}z_{ij}>=1- alpha(3) z_{ij}= 0 or 1 i=1,...,6 j=1,...,6 (4) x,y >= 0 (5)

where M is a large positive constant and *delta* is a small number.

Equation (2) forces z_{ij} to be strictly positive (and hence
one) if ix+jy >= 3. The small number *delta* has to appear since
if it were not present and ix+jy was exactly 3 the constraint would be
z_{ij}>=0 so we would be setting z_{ij} to zero rather
than one. The Mz_{ij} term in the (minimised) objective function
(equation (1)) ensures that we never set z_{ij} equal to 1 unless
we are forced to by equation (2).

Equation (3) ensures that the total probability exceeds *1-alpha*
whilst equation (4) is the integrality constraint for z_{ij} and
equation (5) ensures x and y are non-negative.

Note here that our original linear SP has been transformed into a linear mixed-integer program.

Continuous distributions

To see that we can also (sometimes) transform a SP into a deterministic equivalent in the case of continuous probability distributions suppose now that:

- a
_{1}has a normal distribution with mean A_{1}and standard deviation D_{1}, i.e. N(A_{1},(D_{1})^{2}); and that - a
_{2}has a normal distribution with mean A_{2}and standard deviation D_{2}, i.e. N(A_{2},(D_{2})^{2})

We shall, for ease of explanation, assume a_{1} and a_{2}
are independent. The changes needed if they are not independent are not
significant.

Then consider the left-hand side (a_{1}x + a_{2}y) of
the constraint Prob(a_{1}x + a_{2}y >= 3) >= *1-alpha*.
As this is the sum of two normally distributed independent variables it
also has a normal distribution with mean A_{1}x + A_{2}y
and standard deviation [(D_{1}x)^{2} + (D_{2}y)^{2}]^{0.5}.

Hence the constraint Prob(a_{1}x + a_{2}y >= 3) >=
*1-alpha* concerns the probability that a normally distributed value
(a_{1}x + a_{2}y) is greater than or equal to 3. This can
be addressed in the standard way for normal distribution probability calculations.

Let K be the value of the standard (mean zero, variance one) normal
distribution N(0,1) which has a probability of exactly *alpha* of
being exceeded (e.g. if *alpha*=0.025 then K=1.96). Such values are
easily obtained from statistical tables.

Then standardising we must have that:

Prob(a_{1}x + a_{2}y >= 3) >= *1- alpha*
is true if and only if

[3 - (A_{1}x + A_{2}y)]/[(D_{1}x)^{2}
+ (D_{2}y)^{2}]^{0.5} >= K

i.e. [3 - (A_{1}x + A_{2}y)] >= K[(D_{1}x)^{2}
+ (D_{2}y)^{2}]^{0.5}

i.e. our original probabilistic constraint

Prob(a_{1}x + a_{2}y >= 3) >= *1-alpha*

is equivalent to the nonlinear deterministic constraint

[3 - (A_{1}x + A_{2}y)] >= K[(D_{1}x)^{2}
+ (D_{2}y)^{2}]^{0.5}

so that our SP now becomes:

minimise 5x+6y subject to: [3 - (A_{1}x + A_{2}y)] >= K[(D_{1}x)^{2}+ (D_{2}y)^{2}]^{0.5 }x,y >= 0

Hence our original linear SP has been transformed into a nonlinear program.