The example on this page is from the field of stochastic programming. Some of the parameters of a situation are originally not known with certainty, however, probability distributions for their values are given. Certain decisions must be made before the random variables are realized. After they are realized, other decisions may be made. The latter are called the recourse decisions, and this type of problem is called decision making with recourse. We use the Jensen LP/IP add-in to solve the example, thus providing an illustration of the L-shaped method.

This example was borrowed from An Optimization Primer, An Introduction to Linear, Nonlinear, Large Scale, Stochastic Programming and Variational Analysis, by Roger J-B Wets, January 11, 2005 (unpublished manuscript). A separate section of this site considers Stochastic Programming in detail.

Consider a product mix problem. A furniture maker makes four products: P1, P2, P3 and P4. Two manufacturing resources are required: carpentry and finishing. The requirements measured in hours per unit are known and shown in the table below along with the profit per unit of product.

Our problem is to select the product mix to maximize total profit, but the availability of the resources are not known. Rather we have four equally likely estimates of the hours available for each resource.

The mix chosen will require some number of hours for the resources. Depending on the amount that is available we will pay for extra hours to obtain the necessary number of hours.

This is called a decision making with recourse. We must chose the mix before the uncertain quantities are known. Once the uncertainty is realized we must make additional decisions, called the recourse decisions, to adjust for the new conditions. We use the notation below to describe the model with accuracy. For the example the possible values of the random variables are given in the table above. The probabilities associated with these values are 0.25.

Expected Value Model

One strategy for the decision maker would be to used the expected values for the uncertain parameters and solve the resultant deterministic model.

For the example, the expected time available for carpentry is 5625 hours and the expected time available for finishing is 4000 hours. We use these as the RHS for the two resource constraints (Carp. for carpentry and Fin. for finishing) in the model below. The optimum solution produces 1320.7 units of P1 and 38.043 of P2 for a profit of $20,761.

The solution is really not very acceptable because it does not tell how to respond to the constraints when the RHS values become known. The solution uses all of the expected hours of carpentry, but what happens if the hours available become greater than the expected value? Will those hours be wasted, or should there be additional production?

What if the resource hours available are less than the expected values? Then the solution is infeasible unless some means is found to increase the hours available. In the following we assume additional carpentry hours can be purchased for $5 per hour and additional finishing hours can be purchased for $10. Shouldn't the possibility of purchasing extra hours be considered for the production decisions?

The answer is provided by stochastic programming, but at the price of a much larger model. We use the side model feature to express this more complex situation.

Recourse Model

The recourse model considers all possible values of the random variables. A scenario describes a value for each uncertain parameter, in this case a value for each resource availability. For example we identify scenario 1 with the values (4800, 3936), the amounts available of the two resources. Considering all possible values of the two random variables there are 16 scenarios for the example. Since the resources are independent random variables and since the different values are equally likely, the probability of each scenario is 0.25*0.25 = 0.0625.

The model provides variables for the recourse decisions. The decisions about product amounts must be first. Then the availabilities of the resources become known. If the product requirements are greater than the available amounts, extra resources must be obtained and a penalty is paid. For this example the total penalty is linear with the extra resource. The second term in the objective function is the expected cost of the recourse decisions.

To use the side model representation we restate the problem with a master problem and a collection of subproblems. Each subproblem represents a scenario.

The Math Programming add-in, constructs the master model first. Note we have chosen the Jensen LP/IP Solver.

Select the Side Model option and fill in the dialog below. Clicking the scenario box indicates that this is a stochastic program.

The side model is constructed on the worksheet. Each row starting at row 31 represents a scenario. Equally likely probabilities are automatically generated in column I. These numbers may be replaced when the scenarios are not equally likely. We have inserted the scenario availabilities as the RHS values in columns T and U. The overtime costs are on cells N30 and O30. The constraint equations are automatically placed in columns R and S. The value computed in P28 is the expected value of the recourse solutions. The formulas in the yellow regions of the form are automatically inserted. The user provides the information in the cells with a white background.

Clicking the solve button at the top of the page has different results for the Excel Solver than or the Jensen LP/IP Solver. In the latter case, as illustrated here, a dialog is presented offering various solution options.

The first reads the master and side problems into the LP/IP solver and solves them as a single linear program. The results are shown below. The solver returns the solution in the green regions of the worksheet. The value of the combined master and side models is in cell F4. This quantity is maximized. The recourse decisions depend on the scenario and are presented in columns N and O. The solution is somewhat different than the expected value solution. The objective function is smaller that for the expected value solution because the latter does not recognize the uncertainty in the supply of the resources. The profit for the product sales is reduced by the expected recourse costs.

The model with recourse has 34 more variables and 32 more constraints than the master problem without recourse. Using the side model to represent the scenario problems makes the models easy to express. Additional scenarios are easily added simply by increasing the number of rows in the side model. The Change button on the side model form provides this option.

The recourse models of stochastic programming can become very large. The number of scenarios is the product of the number of uncertain parameters and the number of discrete possibilities. Large models can be represented on an Excel worksheet, but only relatively small models can be solved with the free version of the Excel Solver. It can handle only a limited number of variables and constraints. Versions of Solver with much greater capacities can be purchased from Frontline Systems Corporation. Even with the capabilities that come with every copy of Excel, small problems can be constructed and solved. This is certainly useful for academic exercises.

We have modified the Jensen LP/IP Solver to incorporate the L-shaped method. The new solver can solve models with many subproblems and many variables using a decomposition method. We use the example above on a later page to describe this method. To use the L-shaped method the side models must be linear with no integer variables.

The Jensen LP/IP Solver can also solve the Master and Side problems together as a single LP. The side models can incorporate integer variables. The dimensions of the model are essentially limited only the restrictions of Excel (except the number of integer variables is limited to 50), but the time of solution may be excessive.