next up previous
Next: About this document Up: A Scenario Approach to Previous: Extended Example

Scenario Optimization

The key to this approach is to create a set of scenarios: if the problem for each scenario is a linear program, then the linear programs can be combined into one large problem. The smaller linear programs are linked by variables corresponding to decisions that occur before it is known which scenario is active.

One drawback of this approach is that the combined linear program can get very large if there are a lot of scenarios. For instance, suppose we think that demand for low and high machines is best modeled by a pair of random variables with a given correlation (say demand had correlation .5) that are uniformly distributed between 1000 and 3000. Then there are an infinite number of scenarios, which leads to a very large linear program!

Scenario based optimization can still be used in this situation, however. The key is to generate a finite number of possible outcomes and optimize the decisions over those possibilities. In this case we could generate 100 different low and high demand pairs, create the linear program as given in the previous section, and find the best decision relative to those scenarios. In general, as long as we generate ``enough'' scenarios, the resulting decision will be a pretty good one (though this clearly is an example of heuristic decision making).

Finally, the resulting linear program can be solved using techniques similar to our column generation techniques: while the linear program is very large, there are techniques available to make it easier to solve.

This approach is getting much more attention as financial portfolios are being created in this way, leading Wall Street to take intense interest in large scale linear programming and other aspects of computational mathematical programming.

Michael A. Trick
Wed Nov 20 11:42:00 EST 1996