When we recognize the possibility of uncertainty or risk within the context of mathematical programming, the decision problem might be written as below. The model is shown in the typical matrix format for an LP except tildes appear over all the parameter matrices. This implies that all may be affected by a vector of random variables. In practical instances the model could be complicated by nonlinear terms and integrality restrictions. In any event, the model as stated, is not well defined because: (1) the timing of the decisions and observations of the randomness are ambiguous and (2) what is meant by an optimal solution and a feasible solution is unclear.

Stochastic programming addresses the first issue by explicitly defining the sequence of decisions in relation to the realization of the random variables. Given the sequence, an objective function is defined that reflects a rational criterion for evaluating the decisions at the time they must be made. Feasibility conditions must be adapted to the fact that decisions made before the realization of randomness may have feasibility consequences after the realization. How the issues are resolved leads to the several different problems considered in this section. No single problem formulation is sufficient.

For this section we assume that the probability distribution of is known. More properly we should say that stochastic programming is decision making under risk, reserving the phrase decision making under uncertainty for those situations for which probability distributions are unavailable. We will, however, use the more popular term, uncertainty, to refer to situations in which distributions are known.

For stochastic programming, some variables are to be set by a decision maker, these are the decision variables, while some model parameters are determined by chance, and these are the random variables. There are a variety of situations one might consider in this context. One differentiation is based on when the decision maker must make decisions relative to the time when the random variables are realized. There are several possibilities. Links on the titles go to pages in this section. Some of these descriptions are simplified from more general situations described in more advanced sources.

Wait and See: The decision maker makes no decisions until all random variables are realized.

No Recourse: The decision maker must choose values for the decision variables before any of the random variables are realized. There is a risk of violating the constraints.

Chance Constraints: This is the no-recourse situation when only the RHS vector is random. Solutions are found with specified risks of constraint infeasibility.

Simple Recourse: This topic considers the problem with a random RHS vector. The decision maker must choose values for the decision variables before the RHS values are known, but variables adjusting to the RHS variation are set after the realization. Penalties for constraint violation are specified. A section on Approximations indicates how continuous probability distributions can be approximated for this analysis. An Aircraft Allocation example describes one of the first problems addressed by stochastic programming.

Recourse: Some of the decision variables must be set before the random variables are realized, while others may wait until after they are realized. Models explicitly represent the initial decisions and all recourse decisions. Although the models can be very large, optimum solutions solve for all possible circumstances. A Capacity Expansion example shows that small problems sometimes result in very large models.

Multistage Recourse: Decisions and random variables are determined in stages. The first set of decision variables must be fixed before all realizations. Then the first set of random variables are realized and the second set of decision variables are fixed. The process continues through a series of decisions and realizations. Typically the stages represent intervals of time. We do not consider this situation.

This section addresses some of the relatively simple problems of stochastic programming, those that we might be able to approach with our Excel add-ins. Along the way we provide examples of situations involving uncertainty. There is a great deal of high-level research in this field attempting to extend the bounds on the variety of problems that can be practically solved. Most solutions require high-power computation. The research and the computation are beyond the capabilities of this author and also of Excel. The reader interested in pursuing this subject further should visit the Stochastic Programming Community Home Page.

Uncertainty, or risk, is modeled using random variables and probability distributions. In this section, we often use the features of the Random Variables add-in, particularly the Functions feature. A page is provided in the random variables section summarizing some of the results of this section. We assume in the following some familiarity with probability theory and the Random Variables add-in. Many of the models constructed in this section use the Side Model feature of the Math Programming add-in.

The materials here are partially based on the unpublished manuscript An Optimization Primer, An Introduction to Linear, Nonlinear, Large-Scale, Stochastic Programming and Variational Analysis, by Roger J-B Wets, January 11, 2005. Suggestions and notes from University of Texas colleagues David Morton and Lisa Korf were very helpful.