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.
Recall the problem we had before:
minimise 5x+6y
subject to:
Prob(a1x + a2y >= 3) >= 1-alpha
x,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.
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 zij using:
zij = 1 if when a1 takes the value i (i=1,...,6) and
a2 takes the value j (j=1,...,6) ix+jy>=3
= 0 otherwise
Let pij represent the probability that a1 takes the value i (i=1,...,6) and a2 takes the j (j=1,...,6). Obviously pij=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(a1x + a2y >= 3) >= 1-alpha
x,y >= 0
the deterministic equivalent is:
minimise Mzij + (5x+6y) (1)
subject to:
zij >= [(ix+jy)-3+delta]/M i=1,... ,6 j=1,... ,6 (2)
SUM[i=1,...,6] SUM[j=1,...,6] pijzij >= 1- alpha (3)
zij = 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 zij 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 zij>=0 so we would be setting zij to zero rather than one. The Mzij term in the (minimised) objective function (equation (1)) ensures that we never set zij 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 zij 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.
To see that we can also (sometimes) transform a SP into a deterministic equivalent in the case of continuous probability distributions suppose now that:
We shall, for ease of explanation, assume a1 and a2 are independent. The changes needed if they are not independent are not significant.
Then consider the left-hand side (a1x + a2y) of the constraint Prob(a1x + a2y >= 3) >= 1-alpha. As this is the sum of two normally distributed independent variables it also has a normal distribution with mean A1x + A2y and standard deviation [(D1x)2 + (D2y)2]0.5.
Hence the constraint Prob(a1x + a2y >= 3) >= 1-alpha concerns the probability that a normally distributed value (a1x + a2y) 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(a1x + a2y >= 3) >= 1- alpha is true if and only if
[3 - (A1x + A2y)]/[(D1x)2 + (D2y)2]0.5 >= K
i.e. [3 - (A1x + A2y)] >= K[(D1x)2 + (D2y)2]0.5
i.e. our original probabilistic constraint
Prob(a1x + a2y >= 3) >= 1-alpha
is equivalent to the nonlinear deterministic constraint
[3 - (A1x + A2y)] >= K[(D1x)2 + (D2y)2]0.5
so that our SP now becomes:
minimise 5x+6y
subject to:
[3 - (A1x + A2y)] >= K[(D1x)2 + (D2y)2]0.5
x,y >= 0
Hence our original linear SP has been transformed into a nonlinear program.