Stochastic Programming - Recourse Example: Capacity Expansion

To illustrate a recourse problem, we consider a capacity expansion problem that has the form of a transportation problem. This example was contributed by David Morton at the University of Texas.

A company will supply electricity to three demanders from two electric generators. The unit cost of supplying each customer from each generator site is given below.

 Transport Cost Dem. 1 Dem. 2 Dem. 3 Gen. 1 4.3 2 0.5 Gen. 2 7.7 3 1

The amounts required by the three demanders is uncertain. Each demand has three levels with amounts and probabilities given below. The probability distributions are independent.

Demand/ Probability
Dem. 1
Dem. 2
Dem. 3
Level
 P()
 P()
 P()

1

 900 0.35
 900 0.35
 900 0.35
2
 1000 0.55
 1000 0.55
 1100 0.55
3
 1300 0.1
 1250 0.1
 1400 0.1

To supply the electricity, the company will install capacity at the two generators. The first-stage decisions are and , the installed capacity at the two generators. The unit costs of installed capacity are \$400 and \$350 at generator 1 and 2 respectively. The total capacity cannot exceed 10,000.

The reliability of the installed capacity is uncertain. The fractions and are the proportions of the installed capacity that will actually be available for satisfying demand. There are three levels of reliability as given in the table. These probability distributions are independent. They are also independent of the demand random variables.

Reliability/ Probability
Reliability 1
Reliability 2
Level
 P()
 P()

1

 1 0.9
 1 0.85
2
 0.95 0.05
 0.8 0.1
3
 0.3 0.05
 0 0.05

The decision maker must select the generator capacity to install before knowing the demand or reliability. The second-stage decisions are the decisions about which demands to service from the generators. In the following is the demand satisfied at customer j from generator i. We add a third supplier, Subcontract, to represent demand not met from the generators. The cost can be viewed as a penalty cost or as the cost of satisfying the demand through a subcontractor.

The problem has the form of a transportation model as shown below with random variables and decisions affecting the supplies and demands.

 Transport Cost Dem. 1 Dem. 2 Dem. 3 Supply Gen. 1 4.3 2 0.5 Gen. 2 7.7 3 1 Subcontract 6000 6000 6000 no limit Demand

The transportation model cannot be immediately solved because its parameters depend on five random variables and two decisions determined elsewhere.

The Recourse Model

To find the optimum values of the generator capacities, we setup a recourse model. The first-stage problem is to select capacities for the generators.

 First-Stage Model

The second-stage problem is to distribute the electricity.

 Second-Stage Model

The two models can be combined to form a deterministic linear programming model that represents all 243 combinations of the random variables explicitly. This model has 2,189 decision variables and 1,216 structural constraints. The free Solver that comes with Excel is not able to solve a problem of this size, but it is possible to set the problem up using the Math Programming add-in. The problem may be solved with the L-shaped method available through the Jensen LP/IP add-in. The master problem describes the variables for the generator capacity and the limit on the maximum capacity. The second constraint shown is irrelevant. The arbitrary solution (2000,1000) is shown for illustration.

The side model has a row for each scenario. To reduce the width of this page we show the model in two parts. Only 20 submodels are shown, but there are 243 in total. The part of the model representing the transfer variables (generator capacities) and subproblem variables (distribution decisions) is shown below. To optimize the subproblems for the given master problem solution, click the Solve button near the top of the worksheet and then choose the Solve Side Problem option of dialog.

The optimum solution for the first 20 sub models is shown in the green cells below. Ths solution depends on the variable values chosen for the master problem (2000, 1000).

The remainder of the form shows the constraints of the subproblems. The relations are entered in row 32. The RHS values are different for each scenario and are prescribed in columns AD through AH. The yellow fields in columns Y through AC show the value of each constraint for the current solution. Comparing the constraint values to the RHS values will show that all subproblem solutions are feasible. If some subproblem has no feasible solution, the corresponding solution row has "***" in the solution cells. When this happens, the remaining sub models are not computed and the solution is meaningless.

Solving the Problem

When the Solve button at the left of the master problem is clicked the problem is solved (assuming it is feasible and not too large). If the Excel Solver is used to find the solution, the model of the entire combined master and subproblems is formulated and solved with the Excel Solver. For the current example, this option will not work because the free solver thant comes with Excel can only solve small problems. More advanced solvers available from Frontline Systems can easily solve problems of this size.

When the Jensen LP/IP is the solver of choice, the dialog below is presented. The first option of the dialog is to solve the combined master and subproblems with the simplex method. The LP/IP solver has no built-in limits on the size of the problem and the add-in will attempt to solve the problem. The complete problem was solved on the authors Apple IBook computer running Excel 2007 under the Vista operating system solved the problem in about three minutes. Using Excel 2003 with the Mac OS 10.4.11 operating system took considerably longer.

The second option calls a decomposition algorithm called the L-Shaped Method. These results are demonstrated below. The third option solves only the Master Problem neglecting the subproblems. The fourth option solves the side problem for a given master problem solution.The last two options are considerably easier than solving the combined problem.

L-Shaped Method

By choosing the decomposition option, the add-in presents the L-shaped algorithm dialog. This method is described more fully in the section on Side Models for the Math Programming add-in. The dialog below specifies that the output is to include the cut constraints along with the final solution.

After 13 optimality cuts and 7345 simplex iterations requiring 21 seconds on the author's computer we obtain the solution below. This is not the optimum because a gap of 2.66 remains between the lower and upper bounds. The tolerance is controlled on the dialog.

The subproblem solutions are shown on the side models. Only 20 sub models are shown.

The last three recourse variables are introduced so that every sub model has a feasible solution. Each has a large objective coefficient (6000) that penalize solutions that have nonzero values for one or more of these variables. They represent infeasibility conditions with regard to the original problem statement. We see for example that scenario 7 has nonzero values for y31 and y32. This scenario has a reliability of 0.3 for generator 1 and it is impossible to meet the combined demand of 2700. The side problem is infeasible for this scenario, but the variables y31 and y32 allow the submodel to have a feasible but costly solution. We have summed the probabilities of the feasible scenarios for the Feasible Probability values below.

Summarizing the solution we have.

It is interesting to compare this result with the optimum solution obtained with GAMS running on a workstation. The L-shaped solution is within the specified tolerance of the optimum. We could find a better solution with a smaller tolerance, but more iterations of the method would be necessary.

We compare these solutions with the solutions from several other strategies below.

Transportation Model

For the solutions above, we used the LP form of the transportation model. The side model construction does not work when the master problem is a transportation model. We can use the transportation model, together with the random variables add-in, to find solutions that recognize the stochastic nature of the situation.

We construct the transportation model using the Math Programming add-in. In the figure below, the range enclosed by the bold outline is the original model. The information outside the outline relates the stochastic problem to parameters of the transportation model. The worksheet also includes information not pictured. This is described later.

The maximum supply in the range H11:H13 and the minimum demand in the range D14:F14 are controlled by the first-stage decisions and the values of the random variables. The figure shows one sample point for the random variables and one solution for the first-stage decisions. We show representative equations on the figure. We illustrate the computation with x = (2000,1000). These values are in K11 and K12.

The values of generator capacities are in cells K11 and K12. The values of the reliabilities are in cells M11 and M12. These are transferred by equation from cells D27 and E27. The products of the capacities and reliabilities determine the upper bounds on shipments in cells H11 and H12. The upper bound for subcontracting is set to a high value so that it is not limiting. The demands are placed as lower bounds to shipments in cells D14, E14 and F14. These values are transferred by equations from cells F27, G27 and H27. The cost of the solution has two parts. The installation cost is computed in cell L14, and the operating cost transferred from F4 to L15. The total cost is in L16. In L17 we place a logical expression that computes to FALSE when the amount shipped from the Subcontractor is greater than 0. The transportation model has a feasible solution for all x, but the generator capacities are feasible only when no subcontractor shipments are necessary.

At the bottom of the worksheet we see cells that are not part of the transportation model, but are used to specify values for the random variables. Row 26 has index values that range from 1 to 3. Row 27 has the corresponding values of the random variables taken from the table in rows 29 through 31. The index values are provided by the enumeration form described below.

The Expected Cost

For a given x, we compute the expected value of the recourse problem. We use the Functions feature of the Random Variables add-in for this purpose. Read the linked sections for the details. To create a form choose Function from the add-in menu to display the dialog below. Use 5 as the number of random variables and 2 as the number of functions. The probability values are given by User distributions. The word Network identifies the Jensen Network Solver to be used to solve the transportation model.

The form is constructed as below. For the example, we have placed it immediately to the right of the transportation model. The five distributions are at the top of the form. Rows 16 through 24 are used by the enumeration process. Rows 25 through 33 define the functions to be evaluated and the results. This form is set to find the expected cost and the probability that the given value of x results in a feasible solution.

To find the expected value of the transportation solution we enumerate all possible values for the random variables. Since each random variable has three values there are 3 to the fifth power, or 243, combinations. This is accomplished by selecting the Moments command from the menu. The program runs through all combinations of the random variables. The values for each combination are placed on the transportation model and the model is solved with the Network add-in. The Random Variables add-in then combines all these results to find the expected cost and the probability of a feasible solution. These are in Q32 and R28 respectively.

For the example we have:

The same process is used to compute several other solutions below. For each we place the values of x in cells K11 and K12. Then we choose Moments from the menu to compute the expected value.

Expected Value Strategy

For this solution, we replace the random variables with their expected values. The model then becomes a deterministic linear program. The expected values of the random variables are computed with the usual formulas for discrete random variables.

 Expected Value Model

The expected value solution places capacity only at generator 2. The expected cost and feasibility probability are computed with the Moments command.

Scenario Analysis Strategy

For this strategy we solve the problem with a wait-and-see approach and record the solution vector for each combination of the random variables. This involves the solution of 243 separate transportation models. We then combine the solutions by weighing each solution by the probability of the combination and summing the results. That solution is then used for the first-stage decisions.

Summary

Comparing the three solutions on this page we note that the optimum solution and the nearly optimum L-Shaped solution dominate the other two in that it has a smaller cost and a greater probability of feasibility.

 Solution Objective Value Feasibility Probability Optimum Solution 1,927,687 0.902 L-Shaped Algorithm Solution 1,927,689 0.902 Expected Value Strategy 2,433,951 0.700 Scenario Analysis Strategy 2,629,301 0.466

Operations Research Models and Methods
Internet
by Paul A. Jensen