Computation - Stochastic Programming - Part 2

No Recourse

With the no recourse situation, we must fix the decision variables before the random variables are realized. On this page we investigate some simple strategies for finding solutions. We will finally conclude that these strategies are not very satisfactory. The following pages suggest better, but more difficult, solution methods.

One strategy is to replace the random variables by their expected values and solve the resultant deterministic model. We might ask how well this expected value solution serves as the solution to the stochastic problem. The expected value solution to our example problem is shown below. Since the expected values of the random variables are 0, the RHS values are just the constants originally proposed.

To evaluate this solution in a stochastic setting, we create a function model below the LP model. We create the model by calling the Function command of the Random Variables add-in. Five random variables are defined, each with a Normal distribution. Note that the algorithm field is blank. We use the Include Address option.

The LP model is the same as before, but now we allow the RHS values to vary randomly but do not solve the LP for each sample. For each sample, the solution variables are fixed at the values obtained with the expected RHS. The objective value does not change because the decision vector is fixed. The only question is: What is the probability that this solution will be feasible?

We place logical expressions in G15:G19 to indicate when the constraints are feasible. Cell G31 holds the address of the function value (the objective function of the LP), and cell G33 holds the address of the logical expression that returns TRUE if the solution is feasible and False if it is not. The LP solution on the worksheet is optimal when the RHS values are the expected values, so this solution is feasible. With the Include Address option, cells G32 and G34 are initially blank. They are filled with the appropriate transfer expression when the simulation begins.

When we simulate the model for this case we do not solve the model for every sample. The results are shown below. The objective value shows no variability since the decision variables remain the same for all samples. The proportion of feasible solutions is, however, only 5%. The probability that this fixed solution is feasible is very small.

These results should not be surprising. With the expected RHS values, four of the five constraints are tight in the deterministic optimal solution. Since the RHS values are Normally distributed, there is a 50% that a tight constraint will be violated when the random RHS is realized. Even if the single loose constraint is never violated, the probability that all the tight constraints are satisfied is 0.5 raised to the fourth power or 0.0625. The simulation shows that only 5% if the simulated RHS vectors result in feasible solutions.

One might ask, how should the problem with no recourse be solved? The answer to this question is the provence of stochastic programming.

Combining wait-and-see Solutions

 One suggestion often made for this kind of problem is to solve the problem as if we could wait and see the random realizations and then combine the wait-and-see decisions in some way. We do this for the example by creating a new math programming model identical to the wait-and-see model considered earlier, but create a simulation form that records the values of the decision variables as well as the objective. The form is below. We now have 11 functions defined. The first is the objective function and the remaining ten are the values of the decision variables. All eleven functions have the same feasibility equation. A solution is recorded only when the LP has a feasible solution.

We simulate the random variables, solve the LP for each sample point and record the observed function values. The results from 100 observations is below. None of the solutions were infeasible as indicted by cell G37. This is not surprising since the wait-and-see solutions observe the RHS vector before finding the solution.

Row 39 shows the mean values for the 100 observations. The first entry shows the mean objective value of 125.97. The remainder of the entries on row 39 show the average values of the decision variables. Variables X1, X2, X4, X5, X8, and X10 are nonzero for at least some of the observations.

It is interesting to compare these results against the results for 1000 observations. Row 39 shows that the same set of nonzero variables except for X6. This variable was nonzero for a single selection of random variables.

The first 20 simulated results are shown below to illustrate the variability of the wait-and-see solutions.

The Average Solution

 To continue, we impose the average of the wait-and-see solution on the LP model.

To evaluate this solution, we simulate this model with the solution fixed as above. Of course, since the solution is fixed there is no variability in the objective function. The results of 1000 simulated RHS vectors indicate that the solution is feasible for only 6.5% of the observations.

We have investigated two solutions to the no-recourse problem, the expected value solution and the mean wait-and-see solution. The two solutions are shown in the table. The combined wait-and-see solution has a slightly higher objective value because it is not feasible for the expected RHS vector. Neither fixed solution has a very high chance of being feasible when there is randomness in the RHS vector.

When uncertainty affects the RHS values of the constraint coefficients, there is always a chance that some constraints will be violated by a fixed solution. Choosing a solution involves a tradeoff between the risk of infeasibility and the expected value of the objective function. Chance Constraints, described on the next page, gain some control of the feasibility probability, but again we will be left with a variety of alternative solutions.

Chance Constraints

One way to find a solution that explicitly represents uncertainty is to use chance constraints. Again we use the deterministic solution as a starting point. On a previous page, we discovered that the solution below is not satisfactory if the RHS values are random variables. When the RHS values vary about the mean values according to a Normal distribution with a standard deviation of 10, the solution is feasible only about 5% of the time. One way to find a solution that has a greater feasibility probability is to make the RHS vector smaller. All random variables considered on this page are statistically independent.

One way to provide values for the RHS with known risks of infeasibility is to use the Inverse Probability function of the Random Variables add-in. The worksheet below shows our LP model and also five probability distributions created by the random variables add-in. The random variables are defined in the outlined range starting in row 23. The parameters of the distributions are in columns H and I. We have placed the desired risk of 10% in column J. Column K holds the inverse probability values. For example, there is a 10% chance that the RHS for constraint 1 will fall below 41.1845. This number is computed in cell K24 with the expression:

=RV_inverse(Chance_1,J24)

The number is transferred to the LP model with a formula in cell F15:

=K24

In the figure below, each RHS is set to a value so that there is only a 10% probability of violating each constraint individually. This is easily accomplished by setting the values in the range J24:J29 to 0.1. The deterministic solution shown is optimal for the RHS values shown. The objective value is 94.6. This is quite a bit less than the value of the expected value solution, 125.5, but this solution has a much greater probability of feasibility.

Although the probability of violating each constraint is only 10%, the probability of violating at least one of the six constraints is considerably greater. An estimate of this probability is:

The system risk is computed in cell M30 of the worksheet. The estimate is an upper bound because some constraints may not be tight at the optimum solution, for example, constraint 4 is loose. The estimate for the risk is 0.41 for the present case.

A better measure of system risk is computed at the right bottom of the figure. Here the constraint values obtained by the solution are used to compute the probability that the constraint limits will fall below the values obtained by the solution. The probabilities for the individual constraints are computed as e'. Assuming independence the system risk of 0.381 is computed with the expression.

Levels of Risk

 Different solutions may be obtained with different levels of risk. Several solutions are presented below with increasing objective values and increasing risk. The constraint risk is the number used to determine the RHS values, and the system risk is the probability that the solution will violate at least one constraint. Any number of solutions could added by selecting different values of risk for the several constraints.

In this example, the RHS values are independent random variables and we have included chance constraints for each individual constraint. Since the analyst is probably interested in finding a solution with a given system risk, it would be useful to construct a single constraint that assures this result. This is called a joint chance constraint. Unfortunately, this constraint is not easy to write. For simple cases, it may be possible to write the constraint, but the resultant model is not a linear program. In fact, the feasible region of the resultant model is probably not convex, making the model difficult to solve.

Even if we use only individual chance constraints, there is no general guidance on how to set the risks of constraint violation. The chance constraints do give the analyst a method for explicitly recognizing uncertainty.

Different Forms

 The mathematical model of an LP with chance constraints can be written as below.

As noted above the probability statement can be replaced with a linear constraint with the RHS replaced a constraint evaluated by the inverse probability function. A different form is required for a ">=" constraint. For an equality constraint there is no chance that the constraint will be satisfied for any given solution. So the risk is always 100% for an equality constraint for continuous probability distributions.

We have considered on this page only randomness for the RHS values. When constraint coefficients are random, the situation is more complex.

Simple Recourse

None of the solutions to the No Recourse problem that we have investigated are very satisfactory. When uncertainty affects the RHS values of the constraint coefficients, there is always a chance (assuming unbounded probability distributions) that some constraints will be violated by a fixed solution. Choosing a solution involves a tradeoff between the risk of infeasibility and the expected value of the objective function. The simple recourse model proposes costs of exceeding or falling below the resource amount and finds the optimum solution considering the original objective function and the expected penalty cost. This eliminates the necessity of specifying risk levels, but adds the requirement of accessing penalty costs. 

Deterministic Equivalent

 To explain the simple recourse approach, we consider the linear programming model below. We show a tilde over the RHS vector to indicate that its components are random variables with known probability distributions. We use a minimization objective function for the convenience of the discussion. The methods work equally well for ">=", "<=" and "=" constraints.

The problem, as stated, is not well defined because it does not indicate the time order of decisions and random variable realizations. Also, it does not specify the response of the decision maker when the resources requested by a solution exceed or fall below the amounts available. These issues are addressed on this page.

The decision maker must choose the values of the variables, x, before the random RHS values are known, so this is similar to the no-recourse situation discussed on the previous pages. The situation is, however, a special case of the decision making with recourse problem to be considered later, so we use the term simple recourse to describe this case.

Any kind of linear constraint can be modeled with appropriate unit costs of shortage and overage. For a "<=" constraint the unit shortage cost would be positive and the unit overage cost would be zero. For a ">=" constraint the unit shortage cost would be zero and the unit overage cost would be positive. For an "=" constraint both unit shortage and unit overage cost would be positive. For many practical situations, both costs are nonnegative, but a requirement of the analysis is that the sum of the unit shortage and unit overage costs be positive.

To find an expression for the expected recourse cost we must consider the distribution of the random RHS values. Here we assume a discrete distribution. In the following we drop the constraint subscript, but it will return later. The distribution is defined by a set of K values of the random variable each with a possibly non-zero probability. Values not enumerated have zero probability

For discrete distributions the expected values can be determined by summing.

Combining these relations we find a useful result that allows the determination of one of the expected values given the other.

To construct the model we must divide the amount of resource used into pieces.

It can be shown (but not here) that the expected shortage and overage costs, and hence the expected recourse cost can be computed by a piecewise linear expression.

Combining these relations we obtain an expression for the expected recourse cost.

Math Programming Model

 Finally we replace the expected recourse cost with the piecewise equivalent in the math programming model. Subscripts have been added to represent the expected costs for the several constraints.

When the uncertain RHS values have discrete probability distributions, the equivalent math programming model is linear, and the model is relatively easy to solve. The number of variables is increased by the number of pieces used to represent the expected recourse costs. The constraints are increased by those relating the resource usage to the sum of the pieces and simple upper bounds on the pieces of the expected value representation. The latter don't add materially to the computational difficulty.

An example of this approach for solving simple recourse problems is provided on the next page.

Source: Paul A. Jensen - Operations Research Models and Methods