LINEAR PROGRAMMING UNDER UNCERTAINTY:STOCHASTIC PROGRAMMING WITH RECOURSE

STOCHASTIC PROGRAMMING WITH RECOURSE

Stochastic programming provides an important approach to linear programming under un- certainty that (like chance constraints) began being developed as far back as the 1950's and it continues to be widely used today. (By contrast, robust optimization described in Sec. 7.4 only began significant development about the turn of the century.) It addresses linear programming problems where there currently are uncertainties about the data of the problem and about how the situation will evolve when the chosen solution is implemented in the future. It assumes that probability distributions can be estimated for the random variables in the problem and then these distributions are heavily used in the analysis. Chance constraints sometimes are incorporated into the model. The goal often is to opti- mize the expected value of the objective function over the long run.

This approach is quite different from the robust optimization approach described in Sec. 7.4. Robust optimization largely avoids using probability distributions by focusing instead on the worst possible outcomes. Therefore, it tends to lead to very conservative solutions. Robust optimization is especially designed for dealing with problems with hard constraints (constraints that must be satisfied because there is no latitude for violating the constraint even a little bit). By contrast, stochastic programming seeks solutions that will perform well on the average. There is no effort to play it safe with especially con- servative solutions. Thus, stochastic programming is better suited for problems with soft constraints (constraints that actually can be violated a little bit without very serious con- sequences). If hard constraints are present, it will be important to be able to make last- minute adjustments in the solution being implemented to reach feasibility.

Another key feature of stochastic programming is that it commonly addresses problems where some of the decisions can be delayed until later when the experience with the initial decisions has eliminated some or all of the uncertainties in the problem. This is referred to as stochastic programming with recourse because corrective action can be taken later to compensate for any undesirable outcomes with the initial decisions. With a two- stage problem, some decisions are made now in stage 1, more information is obtained, and then additional decisions are made later in stage 2. Multistage problems have multi- ple stages over time where decisions are made as more information is obtained.

This section introduces the basic idea of stochastic programming with recourse for two-stage problems. This idea is illustrated by the following simple version of the Wyndor Glass Co. problem.

Example

The management of the Wyndor Glass Co. now has heard a rumor that a competitor is planning to produce and market a special new product that would compete directly with the company's new 4 X 6 foot double-hung wood-framed window (“product 2”). If this rumor turns out to be true, Wyndor would need to make some changes in the design of product 2 and also reduce its price in order to be competitive. However, if the rumor proves to be false, then no change would be made in product 2 and all the data presented in Table 3.1 of Sec. 3.1 would still apply.

Therefore, there now are two alternative scenarios of the future that will affect man- agement's decisions on how to proceed:

Scenario 1: The rumor about the competitor planning a competitive product turns out to be not true, so all the data in Table 3.1 still applies.

Scenario 2: This rumor turns out to be true, so Wyndor will need to modify product 2 and reduce its price.

Table 7.12 shows the new data that will apply under scenario 2.

With this in mind, Wyndor management has decided to move ahead soon with pro- ducing product 1 but to delay the decision regarding what to do about product 2 until it learns which scenario is occurring. Using a second subscript to indicate the scenario, the relevant decision variables now are x1 = number of batches of product 1 produced per week, x21 = number of batches of product 2 produced per week under scenario 1, x22 = number of batches of the modified product 2 produced per week under scenario 2.

This is a two-stage problem because the production of product 1 will begin right away in stage 1 but the production of some version of product 2 (whichever becomes relevant) will only begin later in stage 2. However, by using stochastic programming with recourse, we can formulate a model and solve now for the optimal value of all three decision vari- ables. The chosen value of x1 will enable setting up the production facilities to immediately begin production of product 1 at that rate throughout stages 1 and 2. The chosen value of x21 or x22 (whichever becomes relevant) will enable the planning to start regard- ing the production of some version of product 2 at the indicated rate later in stage 2 when it is learned which scenario is occurring.

This small stochastic programming problem only has one probability distribution associated with it, namely, the distribution about which scenario will occur. Based on the information it has been able to acquire, Wyndor management has developed the following estimates:

Probability that scenario 1 will occur = 1/4 = 0.25 Probability that scenario 2 will occur = 3/4 = 0.75 Not knowing which scenario will occur is unfortunate since the optimal solutions under the two scenarios are quite different. In particular, if we knew that scenario 1 definitely will occur, the appropriate model is the original Wyndor linear programming model for- mulated in Sec. 3.1, which leads to the optimal solution, x1 = 2 and x21 = 6 with Z = 36. On the other hand, if we knew that scenario 2 definitely will occur, then the appropriate model would be the linear programming model,

which yields its optimal solution, x1 = 4 and x22 = 1 with Z = 16.5.

However, we need to formulate a model that simultaneously considers both scenarios. This model would include all the constraints under either scenario. Given the probabilities of the two scenarios, the expected value (in the statistical sense) of the total profit is calculated by weighting the total profit under each scenario by its probability. The resulting stochastic programming model is

The optimal solution for this model is x1 = 4, x21 = 3, and x22 = 1, with Z = 16.5. In words, the optimal plan is Produce 4 batches of product 1 per week;

Produce 3 batches of the original version of product 2 per week later only if scenario 1 occurs.

Produce 1 batch of the modified version of product 2 per week later only if scenario 2 occurs.

Note that stochastic programming with recourse has enabled us to find a new opti- mal plan that is very different from the original plan (produce 2 batches of product 1 per week and 6 batches of the original version of product 2 per week) that was obtained in Sec. 3.1 for the Wyndor problem.

Some Typical Applications

Like the above example, any application of stochastic programming with recourse involves a problem where there are alternative scenarios about what will evolve in the future and this uncertainty affects both immediate decisions and later decisions that are contingent on which scenario is occurring. However, most applications lead to models that are much larger (often vastly larger) than the one above. The example has only two stages, only one decision to be made in stage 1, only two scenarios, and only one decision to be made in stage 2. Many applications must consider a substantial number of possible scenarios, per- haps will have more than two stages, and will require many decisions at each stage. The resulting model might have hundreds or thousands of decision variables and functional constraints. The reasoning though is basically the same as for this tiny example.

Stochastic programming with recourse has been widely used for many years. These applications have arisen in a wide variety of areas. We briefly describe a few of these ar- eas of application below.

Production planning often involves developing a plan for how to allocate various lim- ited resources to the production of various products over a number of time periods into the future. There are some uncertainties about how the future will evolve (demands for the products, resource availabilities, etc.) that can be described in terms of a number of possi- ble scenarios. It is important to take these uncertainties into account for developing the pro- duction plan, including the product mix in the next time period. This plan also would make the product mix in subsequent time periods contingent upon the information being obtained about which scenario is occurring. The number of stages for the stochastic programming formulation would equal the number of time periods under consideration.

Our next application involves a common marketing decision whenever a company de- velops a new product. Because of the major advertising and marketing expense required to introduce a new product to a national market, it may be unclear whether the product would be profitable. Therefore, the company's marketing department frequently chooses to try out the product in a test market first before making the decision about whether to go ahead with marketing the product nationally. The first decisions involve the plan (pro- duction level, advertising level, etc.) for trying out the product in the test market. Then there are various scenarios regarding how well the product is received in this test market. Based on which scenario occurs, decisions next need to be made about whether to go ahead with the product and, if so, what the plan should be for producing and marketing the product nationally. Based on how well this goes, the next decisions might involve mar- keting the product internationally. If so, this becomes a three-stage problem for stochas- tic programming with recourse.

When making a series of risky financial investments, the performance of these in- vestments may depend greatly on how some outside factor (the state of the economy, the strength of a certain sector of the economy, the rise of new competitive companies, etc.) that evolves over the lives of these investments. If so, a number of possible scenarios for this evolution need to be considered. Decisions need to be made about how much to in- vest in the first investment and then, contingent upon the information being obtained about which scenario is occurring, how much to invest (if any) in each of the subsequent in- vestment opportunities. This again fits right in with stochastic programming with recourse over a number of stages.

The agricultural industry is one which faces great uncertainty as it approaches each growing season. If the weather is favorable, the season can be very profitable. However, if drought occurs, or there is too much rain, or a flood, or an early frost, etc., the crops can be poor. A number of decisions about the number of acres to devote to each crop need to be made early before anything is known about which weather scenario will occur. Then the weather evolves and the crops (good or poor) need to be harvested, at which point ad- ditional decisions need to be made about how much of each crop to sell, how much should be retained as feed for livestock, how much seed to retain for the next season, etc. There- fore, this is a two-stage problem to which stochastic programming with recourse can be applied.

As these examples illustrate, when initial decisions need to be made in the face of uncertainty, it can be very helpful to be able to make recourse decisions at a later stage when the uncertainty is gone. These recourse decisions can help compensate for any un- fortunate decisions made in the first stage.

Stochastic programming is not the only technique that can incorporate recourse into the analysis. Robust optimization (described in Sec. 7.4) also can incorporate recourse. Selected Reference 6 (cited at the end of the chapter) describes how a computer package named ROME (an acronym for Robust Optimization Made Easy) can apply robust opti- mization with recourse. It also describes examples in the areas of inventory management, project management, and portfolio optimization.

Other software packages also are available for such techniques. For example, Ana- lytic Solver Platform for Education in your OR Courseware has some functionality in ro- bust optimization, chance constraints, and stochastic programming with recourse. LINGO also has considerable functionality in these areas. For example, it has special features for converting a deterministic model into a stochastic programming model and then solving it. In fact, LINGO can solve multiperiod stochastic programming problems with an arbitrary sequence of “we make a decision, nature makes a random decision, we make a recourse decision, nature makes another random decision, we make another recourse de- cision, etc.” MPL has some functionality for stochastic programming with recourse as well. Selected Reference 9 also provides information on solving very large applications of stochastic programming with recourse.