THE VALUE OF THE STOCHASTIC SOLUTION IN STOCHASTIC LINEAR PROGRAMS WITH FIXED RECOURSE by John R. Birge Technical Report 81-10 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 November 1981

THE VALUE OF THE STOCHASTIC SOLUTION IN STOCHASTIC LINEAR PROGRAMS WITH FIXED RECOURSE John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Abstract Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem. Keywords: Stochastic programming, linear programming, expected value of perfect information. Abbreviated Title: Value of the Stochastic Solution. This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-ATO3-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS.7926009 and ECS-8012974 (formerly ENG77-06761).

I. INTRODUCTION Many practical decision problems involve uncertain parameters that are commonly replaced with approximations and expected values. Stochastic programming approaches are generally avoided because, to the practitioner, they appear to multiply the complexities of already complex situations. Sensitivity analyses and deterministic solutions for different scenarios are typically used to determine the effects of changing situations. In attempting to make the explicit consideration of uncertainties more practical, this paper presents an analysis of the expected return from solving a stochastic program instead of deterministic scenarios. We also show that information about this return can be gained in simple extensions of the sensitivity and scenario approaches. The criterion in determining the importance of uncertainties in mathematical models has generally been the expected value of perfect information (EVPI). (See Raiffa and Schlaifer (1961)). This quantity represents the maximum amount one would pay in return for complete information about the future. Madansky (1960) first examined bounds for the EVPI in stochastic programs. His results were later enhanced by Huang, Vertinsky, and Ziemba (1977), Huang, Ziemba and Ben-Tal (1977), and Avriel and Williams (1970). Estimates of the expected value of perfect information reveal the potential worth of more accurate forecasts. In situations in which one cannot gather more information about the future, however, it may be more pertinent for decision makers to know how well their deterministic model solutions perform relative to solutions from more complicated stochastic programs. For this reason, we investigate a quanitity we call the value of the stochastic solution (VSS).

2 To motivate our development, we first show that the EVPI and VSS are distinct, different values that measure different types of uncertainty. We then review basic inequalities for these quantities and present upper and lower bounds on VSS that can be found by solving linear programs at most twice the size of the expected value linear programs. These procedures should be more efficient than direct techniques for large stochastic recourse problems. II. THE STOCHASTIC LINEAR PROGRAM WITH RECOURSE. Dantzig (1955a) and Beale (1955) first formulated versions of the stochastic linear program with fixed recourse. We begin a discussion of this problem by formulating the program: (1) Minimize q(xl, C) = clX1 + Min[c2x21 A2.; = + B1xl, x2 > 0] Subject to A1x = bl x > O0 n n m1 1 2 1 where the vectors cl ~ R, c2 c R, and b c R, are known, the m2-vector, i, is a discrete random vector defined on a finite sample space E, and A1, B and A2 are known matrices. The decision vector xl represents decisions made in the first period, and x2,-a random vector, represents decisions in a future, second period after the first period decisions have been made. A perfect information solution would choose optimal first period decisions in (1) for each realization of i. The expected value of this solution

3 is known in the literature as the "wait-and-see" (WS) solution(Madansky (1960)), where: (2) WS = E [Min V(x1, 0)] X1 An alternative problem, called the stochastic program with fixed recourse by Walkup and Wets (1967), or the recourse problem (RP) by Avriel and Williams, is written: (3) RP = Min E [((xl )]. x1 We note that our assumption of a discrete random variable limits the generality of this program. This should not be too restrictive here since discrete distributions are generally assumed in practical situations. Letting i, i,...,k be the possible outcomes of i, we can write (3) as: 1 1 k k RP = Min c1 x1+ 2 2 + p c2x2 Subj. to A1 xl = b (4) - B1 x1 + A2 x (4) - 2 2 2 - B 1 + A2 2 -B x +A k k B1 1 + 22 X2, x2 > 0, i=l,...,k, where p- = P{ = S}.

4 We also note that the more general recourse problem, as surveyed by Wets (1974), includes randomness in B1, A2, and 2. We can include this 1 k in program (4) by adding components to vectors x2,...,x2 and increasing the number of scenarios (realizations of 5). (For example, if x (j) can 1 2 be carried as inventory to the second period according to B (j) or Bl(j), *i ~ ~~2 1 i then we add x2(n2 + 1) and A2(n2 + 1) = Bl(j) - Bl(j), where x2(n + 1) = for 1 k i k+l 2k xl(j) for i,...,~, and x2(n2 + 1) = 0 for k l..,. These additions again greatly increase the size of the problem. To avoid this, our emphasis will be on using solutions to less complex problems to gain information about the solution of problem (4). The recourse problem is almost always avoided in practice because of the number of possible realizations and the resulting large size of (4). The approximation problem most often solved is the expected value problem: (5) EV = Min 4(xl, E(g)). x1 Letting E(g) =, this program yields first period solutions, x1(g) which multiplied by B1, become inventories, B1 xl, to the second period. A second optimization must then be performed after 5 is realized. We have: (6) (x1 (),I ) = cl x1() + Min[c2 x21 A2 x2 = + B1 x1(), x2 > 0]. We assume here that if no feasible x2 exists, then 4(Xl (), 0) = + o.

5 The expected result of using the EV solution is then (7) EEV = E; [(xl (i), ) ]' In his analysis of this and the other quantities above, Madansky (1960) established the following inequalities: (8) EEV > RP > WS > EV. These results follow directly from Jensen's inequality and the convexity of )(x1, i). III. THE RELATION BETWEEN THE VALUE OF PERFECT INFORMATION AND THE VALUE OF THE STOCHASTIC SOLUTION. Analyses of the effect of uncertainty in stochastic programs generally concentrate on the expected value of perfect information (EVPI). By our definitions, this is: (9) EVPI = RP - WS. We immediately see from (8) that (10) 0 < EVPI < EEV - EV. These bounds are easily computable, as Avriel and Williams (1970) suggest, and can be of substantial benefit in providing bounds on the amount a decision maker should spend to gain more information about the future. More refined upper and lower bounds on EVPI are presented in Huang, Vertinsky and Ziemba (1977) and Huang, Ziemba and Ben-Tal (1977).

6 When no more information about the future can be found, a more useful value may be the difference between the result of using an expected value solution and the recourse problem solution. We call this the value of the stochastic solution (VSS), where (11) VSS = EEV-RP. Frequently, VSS and EVPI are related, but they are not equivalent measures. The appendix presents two simple examples, in which, EVPI = 0 and VSS + 0, and, in which, EVPI 4 0 and VSS = 0. The former example is only possible when multiple optima occur at the minimum solution of EV and may be avoided. The latter situation has, however, been observed in a production problem for a large steel company, and may be relatively frequent in practical problems. IV. BOUNDS ON THE VALUE OF THE STOCHASTIC SOLUTIONo As in the case of the expected value of perfect information, an immediate result of (8) is that (12) 0 < VSS < EEV - EVo When EV = EEV, we therefore have that VSS = 0 and EVPI = 0. Although this result is sufficient for VSS = EVPI = 0, the conditions for VSS = 0 and EVPI = 0 are not the same, as the examples in the appendix indicate. The fundamental difference between the conditions for the two quantities to be zero is that the first period decisions must be independent of the realization of i for EVPI = 0, while VSS can be zero with the first period solution including some information about the second period constraints,

7 To see that these conditions are different we first observe that if there exists some x* and x*(S) such that (x* x* (i)) solves (1), then L 2 )1 2 EVPI = O. To observe that the independence of x* from i can also be a necessary condition for EVPI = 0, we assume that the components of i are nondegenerate independent random variables and that (1) is nondegenerate. In this case, if EVPI = 0, then there must exist x* that solves RP and that is part of a solution to (1) for all i. xl is therefore independent of X and has exactly m1 nonzero components. The nondegeneracy and independence assumptions above are necessary to avoid in which cases x* has more than m1 nonzero components. Even without these 1 1 ro components. Even without these assumptions, this would be an unusual case. In general, then, for EVPI = 0, an optimal basis for each subproblem must have square block triangularity (Dantzig [1955b]). The possibility of multiple optima is, however, an important concern. If multiple optima exists for the expected value problem (1) where i = C and, if x* is not chosen, then the value of the stochastic solution for that choice may not be 0 (as in the example of the appendix). Less restrictive sufficient conditions for having the value of the stochastic solution equal to 0 can be found. To develop these conditions, we first define an auxiliary problem, which we call the pairs subproblem of C and 1

8 (13) Min P((x, ~, = c1 x1 + p c2 x2 (i) + (1 - p) c2 x2 ( ) Subject to: Al xl = bl _ B x + A2 x2() = B x1 + A2 ( ) = x x1 > 0, x2(M), X2( ) > 0, where p P( = ). The pairs subproblem leads to simple sufficient conditions for VSS = 0o We observe that if (1), where 5 = i, has a solution (xl, x*(g)) and there exists some x*(g) for every E such that (xl, x*(t), x2()) solves (13), then clearly x* solves RP and VSS = 0 with 5 substituted for T in the definition of EEVo Finding ~ may prove difficult as many pairs problems must be solvedo We shall restrict ourselves to E = i in the computational discussion, although specific knowledge about a problem may lead to another choice. Intuitively, the conditions for C hold when a single second period scenario requires additional resources from the first period that are sufficient for all other scenarios and when,without these conditions, a costly penalty would arise. We discuss a case in which this situation A - arose and in which 5 = i below. We also note that these conditions show that it is not necessary for xl to be independent of i for VSS = 0. Hence, some information about the future can be incorporated into the solution0

9 The pairs subproblem (13) can also be used to determine bounds on the VSS even when the sufficient conditions do not hold. Since the pairs subproblems are much less complex than the general recourse problem (4), these bounds may be valuable in determining whether the additional computations for the stochastic program are warranted. We first define two quantities to which we will refer. The first SPEV, for sum of pairs expected values solutions, is 1 k. (14) SPEV =c - - p min p(x,, ) where we have restricted ourselves to the simpler discrete case and let ~ = The second quantity is EPEV, for expectation of pairs expected value solutions. For this quantity, we define xl (, ~i) to be the optimal ^ - i first period solution of (13) for W = i, ~ =. We then have (15) EPEV - Min El [(X(', ci), )], i - where we include i = i in the minimization. The EPEV represents the best expected value solution that can be obtained from the problem (13) for all i. To find this quantity, each pairs subproblem and each second period problem (as in (6)) would be solved. This procedure may require several optimizations, but each would be of manageable size. The SPEV and EPEV are related to the RP solution as stated in the following lemmas.

10 LEMMA 1I WS < SPEV < RPo PROOF: Any solution x*, of the recourse problem must have a feasible completion in (13) for all i. Hence, for any optimal solution, (xi, x22(), x2(i)), of (13), we have (16) c1 X + (1 - p) c2 x2(i) < ci 1 + p2 X2 () + (1 - p) c2 x(Si), where x1, x, (x ), x (2),.o0, X (c) are optimal in (4). Taking sums over i and multiplying by pi, we have SPEV < RP. Similarly, every (x1, x2(0)) and (xl x2 (1') found in the pairs subproblem is feasible for the individual problems in (4). Hence, SPEV > WS. S LEMMA 2: RP < EPEV < EEV. - - i -i PROOF: Since E[(x (i, 5 ),P)] = x( ) + c pi C2 x2 - i for x> optimal in the second period problem(6), we have (17) Ey[((x (, ) )] > RP, for all i. Hence, EPEV > RP. The second inequality follows obviously from observing that the solution of (13) for i = i will be the same as in the expected value problem (4) when F = i. The two lemmas above immediately give us the following theorem.

11 THEOREM 1: 0 < EEV-EPEV < VSS < EEV-SPEV < EEV-WS. PROOF: This follows directly from Lemmas 1 and 2 and (8). U The upper bounds on the value of the stochastic solution can be easily calculated by solving the k-l pairs subproblems. These problems should be much less complex than the recourse problem for large k. The result of these optimizations should then be used as a guideline for motivating further effort in solving the recourse problem. If the upper bound is large, more investigation may be warranted, but, if it is small, the expected value solution may be used without significant consequences. We note that the lower bound on VSS provides necessary conditions for VSS = 0. This bound requires more computation in the evaluation of EPEV, but it may be warranted when a large upper bound on VSS has been found. The pairs subproblem solutions here are used in a similar manner to the deterministic solutions in the "modified wait-and-see" approach of Gunderson, Morris, and Thompson (1978). In each case, the best expected value solution for a set of smaller problems has been used as the solution of the larger recourse problem. According to Gunderson, et. al., practical problems suggest that this procedure is reasonable since the majority of first period decisions remain unchanged under varying second period realizations. We believe that pairs solutions are quite valuable here because they can include basic decision variables from either but not both of the scenarios. Our experience on an optimization model for capacity expansion demonstrated the importance of this property.

12 The model was formulated to determine when coke producing facilities should be expanded over an intermediate term planning horizon. Within this model, levels of production at various sites and levels of importation from external sources had to be determined. Random quantities included the demand for coke in each market region and the amount of low and high priced imported coke available. The "worst case" scenario that assumed the highest demand in each market and the most restricted levels of low cost imports led to a first period decision to expand capacity and to produce maximum inventories at each plant. The scenarios that assumed low demand and large supplies of low cost imports led to myopic first period decisions (minimum inventories). The optimal solution to the recourse problem included the expansion of the first period but did not require maximum inventories at all plants. In this case, the expected cost of using high cost imports to satisfy demand for the worst case was less than the cost of producing in the first period to fill the maximum inventories, Solving the pairs problems using the worst case scenario as resulted in EPEV RP but SPEV < RP since the worst case scenarios solution was not part of the solution to RP, Small changes in the cost of imports did, however, make the worst case first period solution optimal in RP and VSS = 0. In this case, also,the expected value solution used the same set of basic activities as the optimal solution, and the "modified-wait-and-see" procedure would have led to an optimal solution,

13 This problem demonstrated that the pairs subproblems could be useful in determining decisions for recourse problems. The substitution of the worst case for 4 was based on the specific problem and the observation that first period production was required to meet future demand. In other examples, information such as that used here may be beneficial in determining which scenarios to use as i. Successively tighter bounds on the value of the stochastic solution can be found by optimizing larger subproblems. In addition to pairs, combinations of three and more scenarios can be used as subproblems to bound VSS. We can obtain these bounds by defining SGEV(Z) as the sum of group expected values with Z scenarios, where k k k i I i2 (18) SGEV(.) 1- p p...a p (1-p) il= i2 >i i i i~>i~ M. i i 1 C Min (xX i, 5 1,..., ), i i i 2 - 1 2 2/ and where 9p(x,,,(;..., i ) is the objective function of the group subproblem: _ i i * (19) Min ( (x1 1, 5 2', ) = cll + p c2x2( + Z (l-p) c2x2 ( J) ij tL subject to: A1 x1 = b, -B1 x1 + A2 X2(() =, i. i. - B x1 + Ax2 X2( j) = i J, j = 1, 2,..., 2, x1, x 2(), x 2( J) > O, j = 1, 2,,..., 2,

14 where, is the set of distinct indijces among il, i2,..., iv. Analogous to EPEV, we also define EGEV(Z) as the expectation of group i i i ) expected values solution with Z scenarios. We define x (j, ~,,,.o, ) as the optimal solution in (19), and obtain i i i (20) EGEV(Q) M Min E[(l(, 1.., 2),. (i1, i2,-..iR) The extensions of lemmas 1 and 2 follow: Lemma 3. WS < SPEV = SGEV(1) < SGEV(2) < ** < SGEV(k-2) < SGEV(k-l) < RP, where E has k possible realizations. Proof: By definition SGEV(l) = SPEV. For (x, x (R), x2 (; ), i2 1 i(Sg 2),..., x2( q)) optimal in (19) with Q = q, and for (xl, x2(g), 2 2 2 1 2 2.2 i i kj j, j=1 _ x q)), SCh~EVre~q) < SGI~(xV'Jq + ) Ayere (xti xsu ) as in x( and xm p b ( q), x p q is optimal in (19) for j = q + 1 and = q + 1, then 1 - (21) c XT + p c2x^(^) + Z (1-p) c^(5 *) < c1x^ + p c x ij~ cL + (A-p) cj xZ[ i). ij 2 L i( i i By taking sums as in (18) and multiplying by p p p we obtain SGEV(q) + SGEV(q + 1).

15 We also observe that for 9 = k - 1, the components of any solution (xx, X2,x,'., x') of (4) which correspond to il, i., ik l in (19) will form a feasible solution to (19). Hence, we obtain SGEV(k -1) < RPo l Lemma 4. RP < EGEV(k - 1) < EGEV(k - 2) < *** < EGEV(2) < EGEV(1) = EPEV < EEV. Proof: We note that EGEV(1) = EPEV by definition, and we observe that any solution considered in EGEV(q-l) is considered in EGEV(q), hence EGEV(q) < EGEV(q-l). EGEV(k-l) > RP also follows directly since any first period solution of (19) with i,, i2,..,i, all distinct must have a feasible completion in (4). V These two lemmas lead directly to: Theorem 2. 0 < EEV - EPEV = EEV - EGEV(1) < EEV - EGEV(2) < *** < EEV - EGEV(k-l) < VSS < EEV - SGEV(k-l) < EEV - SGEV(k-2) < *. < EEV - SGEV(2) < EEV - SEV() EEV - SPEV < EEV - WS. To compute SGEV(Z) and EGEV(k) for groups of many scenarios may lead to more computational effort than is involved in computing the RP solution. In fact, for 9.= k - 1, solving RP is equivalent in terms of problem size to solving one of the group subproblems. These bounds should, therefore, be used only when they add information to the problem without creating many additional computations. Again, we used 5 as a base case for these subproblems but other values of i could be used based on more specific information about the problem.

16 V. SUMMARY. The value of the stochastic solution has been presented as a measure of the benefit received from solving the stochastic recourse problem instead of the deterministic expected value problem. The relationship between this quantity and the expected value of perfect information was presented, and the distinctions between the two differences were noted. Bounds were then given for the value of the stochastic solution that can be computed by solving a series of subproblems that are more computationally tractable than the recourse problem. ACKNOWLEDGEMENT The author thanks Professor George B. Dantzig for his invaluable supervision and guidance. The author also acknowledges the helpful comments of an anonymous refereeo

17 REFERENCES M. Avriel and A. C. Williams, "The value of information and stochastic programming", Operations Research 18 (1970) 947-954. E. M. L. Beale, "On minimizing a convex function subject to linear inequalities", Journal of the Royal Statistical Society B 17 (1955) 173-184. G. B. Dantzig, "Linear programming under uncertainty", Management Science 1 (1955a) 197-206. G. B. Dantzig, "Upper bounds, secondary constraints, and block triangularity in linear programming", Econometrica 23 (1955b) 174-183. H. S. Gunderson, J. G. Morris and H. E. Thompson, "Stochastic programming without recourse: a modification from an applications viewpoint", Journal of the Operational Research Society 29 (1978) 769-778. C. C. Huang, I. Vertinsky and W. T. Ziemba, "Sharp bounds on the value of perfect information", Operations Research 25 (1977) 128-139. A. Madansky, "Inequalities for stochastic linear programming problems", Management Science 6 (1960) 197-204. H. Raiffa and R. Schlaifer, Applied statistical decision theory (Harvard Business School, Boston, 1961). D. W. Walkup and R. Wets, "Stochastic programs and recourse" SIAM Journal of Applied Mathematics 15 (1967) 1299-1314. R. Wets, "Stochastic programs with fixed recourse: the equivalent deterministic program", SIAM Review 16 (1974) 309-339.

1'8 APPENDIX A. An example where EVPI = 0 and VSS $ 0. We consider the following program: Min z = xl + 4x2 + E [min yl + 10y2 + 10y2 | xl and x2] Al.) Subject to: xl + x2 =1 - x! + 2x2 + Yl +y2 Y2 =' 0 < < Y < 2,' x2, Y2 Y > 0, + is Uniform [1, 3]. For the deterministic version of this problem we have the following optimal first period variables and the range of E over which they are optimal. Basic Range (xl, x2) = ( ) [1 3] (x1, x2) = (0, 1) [2, 3]

19 1 2 The solution of the stochastic problem includes (xl, x2) = (3, ). Since this is optimal for all;, we have WS = RP and EVPI = 0. At ~ = 2, however, an alternative optimum exists. If (x1, x2) = (0, 1) is used as the expected value solution, we find (see Figure 1) that (A2.) VSS = 9 4 = 5 We note that large scale problems often include alternative optima and that this example may not be a trivial case. B. An example where EVPI + 0 and VSS = 0. 3 3 We consider (Al) again where E {(0,,3 and P( = 0) = P( = = P(~ = 3) = I. In this example, the optimal basic set of first period variables for the expected value problems is {x1, x2}. These variables are also basic in the optimal recourse problem solution. For (x1, x2) = 2 1 ( -, -), an optimal solution of the expected value problem, we have VSS = 0. 3 3 However, (see Figure 2), (A3.) EVPI = 30

20 4(i1, 0) \ *10\ X1____ ^ chosen optimally 10for all 1 \ - - -. - x1 chosen by recourse N\ problem. | -,-. -.- x1 chosen by expected 3.-.^^~~~~- -^value problem. 0 1 2 3 Figure 1. EVPI = 0, VSS 4 0

217 ~ (Xi, i) 10- o x1 chosen optimally _- ~~~~~~~- ~for all. 0 x chosen by recourse 5 - problem. chosen by expected X 1 value problem. 0 1 2 3 Figure 2. EVPI $ O, VSS = 0.

UNIVERSITY OF MICHIGAN 9011111 11111111111111111195 3 9015 04732 7195