Stochastic Programming Introduction *

Introduction

Stochastic programming is a framework for modelling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within certain bounds, one approach to tackling such problems is called robust optimization. Here the goal is to find a solution which is feasible for all such data and optimal in some sense. Stochastic programming models are similar in style but take advantage of the fact that probability distributions governing the data are known or can be estimated. The goal here is to find some policy that is feasible for all (or almost all) the possible data instances and maximizes the expectation of some function of the decisions and the random variables. More generally, such models are formulated, solved analytically or numerically, and analyzed in order to provide useful information to a decision-maker.

The most widely applied and studied stochastic programming models are two-stage linear programs. Here the decision maker takes some action in the first stage, after which a random event occurs affecting the outcome of the first-stage decision. A recourse decision can then be made in the second stage that compensates for any bad effects that might have been experienced as a result of the first-stage decision. The optimal policy from such a model is a single first-stage policy and a collection of recourse decisions (a decision rule) defining which second-stage action should be taken in response to each random outcome. A good introductory example of such a model is the gas-company example on the NEOS web site, which we summarize below.

Example
The gas company example has a planning horizon of two years. In the first year the gas company buys gas from the market, delivers some to its customers right away and puts the rest in storage for next year. The following year the company can supply from storage or buy from the market. The decision variables are:

1) how much gas to purchase and deliver,
2) how much gas to purchase and store, and
3) how much gas to take from storage and deliver to customers.

The decision depends on the price of gas in year 1 and year 2, the storage cost (say $1 per unit per year), the size of the storage facility, and the demand in each period. With this information the problem can be modelled as a simple linear program with the objective to minimize overall cost. In practice the price and demand in year 2 will be uncertain. Suppose that year 1 is a normal year and that year 2 can be one of three equally likely scenarios: normal, cold, or very cold. Each of these scenarios has different data as shown in the following table:
 
Scenario Probability Gas Cost ($) Demand (units)
Normal 1/3 5.0 100
Cold 1/3 6.0 150
Very Cold 1/3 7.5 180

Forming and solving the stochastic linear program gives the following solution:
 
Year  Scenario Purchase to Use  Purchase to Store  Storage  Cost ($) 
1  Normal 100     100     100     1100 
2  Normal 0     0     0    0 
2  Cold 50     0     0    300 
2  Very Cold 80     0     0    600 

Expected Cost = $1400

Although stochastic programming encompasses a wide range of methodologies, the two-stage gas-company example illustrates some important general differences between stochastic programming models and deterministic models. In the gas-company example there are three equally likely scenarios. A common approach adopted by planners is to seek an optimal policy by computing an optimal solution for each scenario separately. The candidate solutions here are to store either 0 or 180 units of fuel for the next stage. The optimal policy (as delivered by the stochastic program) is to store 100 units. This does not correspond to the optimal solution in any of the scenarios. (It is also different from the storage policy of 143.33 units obtained by solving an optimization problem with averaged data.) The solution from the stochastic program is well-hedged, building in some flexibility to meet the uncertain demand in the second stage.

A second important observation for the gas-company model is that the sequencing of decisions and observations is important. In constructing a stochastic programming model, it is not enough just to specify the decision variables: the modeller must also construct the model in such a way that prevents decisions that anticipate future uncertain events. In the example, if the company could anticipate demand then it would store 0, 0, or 180 units in the first stage depending on the future weather outcome. However this is not an implementable policy.

A third observation about the example is that the objective function in this case does not account for the variation in outcomes. The model minimizes an expected cost, and its optimal policy gives costs of $1100, $1400, and $1700 under each scenario. If this were a one-shot decision then this spread of outcomes might be seen as unacceptable for the gas company owner if they are unwilling to accept some outcome that costs $1700. Modelling different attitudes to risk is possible in the stochastic programming framework by using piecewise linear, or more general nonlinear, objective functions.

Although two-stage stochastic linear programs are often regarded as the classical stochastic programming modelling paradigm, the discipline of stochastic programming has grown and broadened to cover a wide range of models and solution approaches. Applications are widespread, from finance to fisheries management. An alternative modelling approach uses so-called chance constraints. These do not require that our decisions are feasible for (almost) every outcome of the random parameters, but require feasibility with at least some specified probability. For details of this approach see the Introduction to Chance-Constrained Programming by Rene Henrion.

One natural generalization of the two-stage model extends it to many stages. Here each stage consists of a decision followed by a set of observations of the uncertain parameters which are gradually revealed over time. In this context stochastic programming is closely related to decision analysis, optimization of discrete event simulations, stochastic control theory, Markov decision processes, and dynamic programming.

How does stochastic programming differ from these models? In general terms the discipline combines the power of mathematical programming with advanced probability techniques, to attack optimization problems that involve uncertainty. A mathematical programming approach has important benefits: the tools of convex analysis and duality theory can be applied to yield important insights and develop solution techniques based on decomposing large problems into manageable pieces. The tools of mathematical programming are also indispensible in handling general constraints on states and decision variables. (The addition of constraints is often a serious impediment to dynamic programming techniques as it increases the dimension of the state space, which can lead to an intractable problem.) An important (current) restriction for stochastic programming problems - in contrast to dynamic programming problems - is that the probability distributions of the random parameters are assumed to be given, and cannot depend on the decisions taken.

For an excellent introduction to stochastic programming and a discussion of its relationship to related areas see the lecture notes Optimization under Uncertainty (PS) by R.T. Rockafellar.

[Top of page]

Applications

Stochastic programming has been applied in the following areas:

[Top of page]

Solving stochastic programs

Solution approaches to stochastic programming models are driven by the type of probability distributions governing the random parameters. A common approach to handling uncertainty is to define a small number of scenarios to represent the future. For example in the gas company example the random outcomes were modelled by three scenarios. In this case it is possible to compute a solution to the stochastic programming problem by solving a deterministic equivalent linear program. These problems are typically very large scale problems, and so, much research effort in the stochastic programming commmunity has been devoted to developing algorithms that exploit the problem structure, in particular in the hope of decomposing large problems into smaller more tractable components. Here convexity is a key property. Details of these approaches can be found in the recent tutorial talk by John Birge.

When the probability distributions of random parameters are continuous, or there are many random parameters, one is faced with the problem of constructing appropriate scenarios to approximate the uncertainty. One approach to this problem constructs two different deterministic equivalent problems, the optimal solutions of which provide upper and lower bounds on the optimal value z* of the original problem. For details see the tutorial talk by Chanaka Edirisinghe.

An alternative solution methodology replaces the random variables by a finite random sample and solves the resulting (deterministic) mathematical programming problem as one would do for the finite scenario case (see above). This is often called an external sampling method. Under fairly mild conditions one can obtain a statistical estimate of the optimal solution value that converges to z* as the sample size increases. External sampling methods typically take one sample before applying a mathematical programming method. A number of algorithmic procedures (see the second half of the Birge paper) have been developed to take repeated samples during the course of the algorithm. This is often called an internal sampling method. Details of the convergence properties of external and internal sampling methodologies can be found in the recent papers by David Morton (PS) and Alexander Shapiro (PDF).

Stochastic integer programming models arise when the decision variables are required to take on integer values. In most practical situations this entails a loss of convexity and makes the application of decomposition methods problematic. Techniques for solving stochastic integer programming models is an active research area (see the tutorial paper by Rüdiger Schultz (PDF)).

For an overview of SP research, see the list of current research areas which provides links to separate pages for each subject.

There are several sites that the reader may seek further information (and other introductory documents) on stochastic programming. These are listed in SP Resources.

[Top of page]

Links to related fields

This Official COSP Stochastic Programming Introduction was developed by Andy Philpott with the encouragement and support of COSP. Please send comments and suggestions to the Webmaster.

[Top of page]