

Stochastic
Programming 


Wait and See 

To illustrate stochastic programming,
consider the linear programming model below. The solution algorithm
is the Jensen LP/IP addin. The problem was generated randomly
using the Math Programming addin. The solution shown is the
optimum solution when all parameters of the model are deterministic. 


For the examples on this page, we assume that
all parameters are deterministic except the righthandside
vector,
shown in the range F15:F19. The numbers given are the expected
values but we add a random variation for each value that is
distributed
as a Normal variant with mean 0 and a standard deviation of
10.
On this page we investigate the waitandsee policy
in that the random variables are realized before the decision
maker sets
the solution vector x. The solution x is
determined by the solution of the LP. This is not really a stochastic
programming problem because there is no uncertainty when the
decisions are finally made. We might be interested, however,
in the stochastic features of the optimum solution value
and on the feasibility of the model when viewed before the
random variables are realized. On this page we use the Monte
Carlo simulation features of the Random Variables addin
to perform the analysis. 
The Stochastic Model 

The methods of this section are
applied to an optimization model constructed with the math
programming addin. We have created the LP model above on the
worksheet LP1.
To create a stochastic model that describes the random features
of the situation, we choose Function
from the Random Variables
menu and fill in the Add Function dialog as below.
We have specified LP/IP as the algorithm in the field at the
bottom
of the dialog.
This means that the LP will be solved
for each point of the sample space that is generated by the
enumeration or simulation procedure. For the example we use
the Simulate method. 


The form is placed below the LP model as shown
below. The information in rows 22 and 23 give the function
name, F_9, the type of analysis, Simulate, the number
of simulation iterations, 100, and the algorithm to be used
with each iteration, LP/IP.
The random variable definitions
are in rows 25 through 27. All
have
been specified
as Normal
distributions
with
mean values of 0 and standard deviations of 10. The parameters
can be changed on the form. The math programming model
is linked to the random variables via the RHS entries shown
in column F of the LP model. They have been replaced by the
equations in column G (the equations are placed in column
F, but illustrated
in
G). Each RHS is the sum of the original value stored in column
C and a Normal random variable defined on the function form.
As the simulation is performed the RHS values will change
randomly.



Rows 28 through 30
generate the simulated values. The numbers in row 29 (now 0.5)
will be replaced by uniformly distributed random numbers. The
numbers in row 30 compute the simulated values based on the
Monte Carlo method.
Rows 31, 32 and 33 describe the functions to be
observed during the simulation. Cell G31 is the name. The function
value in G32 is an equation that links to the LP objective
in F4. The feasibility value in G33 is
a logical statement that points to cell O4 (shown with the
LP model above). That cell, filled by the LP/IP addin, holds
the word "Optimal" only when the model has a feasible
solution. For each simulation these cells will hold the optimum
LP value and an indication of feasibility. The particular solution
shown has all random variables set to 0,
their expected
values.
The
solution
for
this sample
point is the same as the deterministic solution.
The green cells in the range G34 through G38 hold
the results of the simulation. These are filled in by the addin.
Cell 34 returns the proportion of the observations that are
feasible. Cells G36 and G37 hold the mean and variance of the
simulated function, the LP optimum value in this case. Only
the results for feasible solutions are reported. Cell G38 holds
the number of feasible solutions or the sample size of the
mean and variance statistics immediately above. G39 holds a
confidence level entered by the user, cell G40 holds a confidence
interval computed from the statistics.
To simulate the model choose Moments from
the Random Variables menu and set the number of simulation
observations to 100. Larger values give more accurate results,
but take
more
time. Each simulation iteration draws a random sample from
each distribution. The
values are
reflected
in
the RHS
vector,
and the LP/IP algorithm
solves the problem. 


The results of
100 observations are combined and placed on the form beginning
in row 34 of the figure below. The numbers shown in rows 29 through
33 are for the final simulated observation of the random variables. 



We have simulated 100
observations of the waitandsee option. Even though
the solution is optimum for each simulated RHS, the mean objective
function
(estimated at 121.4217 in cell G36) is lower than the value
when the RHS values were set to the expected values (125.6).
This is a consequence of "Jensen's Inequality" (named
after a different person than the author). The expected value
solution
will always have a higher objective function (when maximizing)
than a solution that explicitly represents uncertainty.
All the observations in the sample of 100 were
feasible for the example and the 90% confidence interval for
the LP objective value is almost 2.5. The
addin displays the random variable values as well as the objective
function values. The first 20 observations are shown below.
It is interesting to increase the standard
deviation of the random variables to 30, thus increasing
the variability of the RHS values. The simulated results are
below.
For this model, the solution is infeasible only if one of
the RHS values is negative. With the data provided, 77% of
the right side values have feasible solutions. The mean objective
value is decreased with significantly greater variance over
the case when the standard deviation values were 10. The 90%
confidence interval is now about 8.25. There is a price to
pay for variability, even with the wait and see policy. 



For the example
shown in the figure, the value of the random deviation for the
fifth constraint is 68.427. This is larger in magnitude than
the mean value of 50. The negative RHS value allows no feasible
solution. The list below shows the first 20 simulated values.
The *** values in column S indicate that there are no feasible
solutions for the associated simulated values. 



On the next and
following pages, we consider the problem of setting the variables before the
random variables are known. 


