MODELS AND MODEL VALUE IN STOCHASTIC PROGRAMMING John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 93-2 January 1993

Models and Model Value in Stochastic Programming John R. Birge* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan, USA 48109 Abstract: Finding optimal decisions often involves the consideration of certain random or unknown parameters. A standard approach is to replace the random parameters by their expectations andc to solve adeterministic mathematical program. A second approach is to consider possible future scenarios and the decision that would be best under each of these scnearios. The question then becomes how to choose among these alternatives. Both approaches may produce solutions that are far from optimal in the stochastic programming model that explicitly includes the random parameters. In this paper, we illustrate this advantage of a stochastic program model through two examples that are representative of the range of problems considered in stochastic programming.The paper focuses on the relative value of the stochastic program solution over a deterministic problem solution. Keywords: stochastic optimization models, finance, quality control, engineering design. * The author's work was supported in part by the National Science Foundation under Grant DDM9215921. 1

1. Introduction Practical decisions often involve the consideration of uncertain or stochastic parameters. Optimization procedures are increasingly helpful as the size and complexity of tractable problems grow. Ignoring fundamentally random characteristics may, however, limit the usefulness of an optimal solution. Stochastic programs that explicitly consider randomness may be much more beneficial for actual operations. The expected objective value advantage of using a stochastic program solution over a deterministic program solution is called the value of the stochastic solution (VSS). In Section 2, we illustrate this quantity through a financial planning model in which one seeks to maximize expected utility concerning a child's higher education. Of particular note is that the VSS is different from the expected value of perfect information which represents the expected objective improvement possible with perfect knowledge of the future. In Section 3, we consider a different type of model from engineering. A part must be designed while considering manufacturing and end-user variability. Here, although the manufacturer is quite likely to realize expected costs with little variance, the substitution of expectations for random quantities within the objective function can be quite costly. Again, the value of the stochastic solution is quite high. Section 4 briefly discusses other application areas and summarizes the conclusions. 2. Financial Planning and the Value of the Stochastic Solution Financial decision making problems can often be modeled as stochastic programs. They represent one of the largest application areas of stochastic programming. Many references can be found in, for example, Mulvey and Vladimirou [17], Ziemba and Vickson [24] and Zenios [23]. We consider a simple example that illustrates basic stochastic programming properties. The random variables reflect uncertain investment yields. The role of the stochastic program is to hedge against poor outcomes by maximizing an expected objective function that is concave and represents some aversion to risk. For the current problem, suppose we wish to provide for a child's college education Y years from now. We currently have $w to invest in any of K investments. After Y years, we will have a wealth of $W that we would like to have exceed the tuition goal of $G. We suppose that we can change investments every y years so we have T = Y/y investment periods. For our purposes here, we ignore transaction costs and taxes on income although these considerations would be important in practice. In formulating the problem, we must first describe our objective in mathematical terms. We suppose that exceeding $G after Y years would be equivalent to our having a future income of i of the excess while 2

Utility or XG Wealth q Figure 1. Utility function for value of wealth above and below goal G. not meeting the goal would lead to current borrowing for a cost q of the amount short. This gives us the concave utility function. Many other forms of nonlinear utility functions are of course possible. See Kallberg and Ziemba [13] for a description of their relevance in financial planning. The major uncertainty in this model is the return on each investment k within each period t. To illustrate the effects of including stochastic outcomes, we use a simple example with K = 2 possible investment types, stocks (1) and government securities (bonds) (2). We begin by setting Y at 15 years and allow investment changes every 5 years so that T = 3. From examining the data, suppose we assume that in each five-year period, it is equally likely to have one of two outcomes: (inflation adjusted) returns of 1.25 for stocks and 1.14 for bonds or 1.06 for stocks and 1.12 for bonds. We first consider the common optimization approach to replace these uncertain quantities by their expectations. Now, if we take expectations, then stocks have an expected return in each 5-year period of 1.155 and bonds have an expected return of 1.13. The remaining data are the initial wealth, w = 55,000, the target value, G = 80, 000, the surplus reward, i = 1, and the shortage penalty, q = 4. The deterministic mean value problem is to maximize the surplus minus penalty over the three periods. The decisions are x(k, t) for investment in k at time t. The resulting linear program is: max v -4s s. t. x(1, 1) + x(2, 1) = 55, -1.155x(1,1) - 1.13x(2,1) +x(1,2)+ x(2,2) =0, -1.155x(1, 2) - 1.13x(2, 2) +x(1, 3) + x(2,3) = 0, 1.155x(3, 1) + 1.13x(3,2) -v +s =80, x(l, 1), x(2, 1), x(1,2), x(2,2), x(1,3), x(2,3), v, s > 0, which clearly has a solution with x(1, 1) = 55, x(l,2) = 63.525, x(l, 3) = 73.372, and v = 4.74 to yield a 3

value of 4.74. This result is, of course, deceiving because the expected return will not occur. If this solution is followed (to invest all funds in stock) withthe two-outcome distribution we assume, then the result is much different in expectation. In this case, we consider each of the eight possible outcomes or scenarios over three periods and weigh each by a probability of 0.125. Now, the return on stock is 1.953 with probability 0.125, 1.65625 with probability 0.375, 1.4045 with probability 0.375, and 1.191 with probability 0.125. Notice that we need a return of 80/55 = 1.45 to reach the goal. Investing in stock alone misses this goal with probability 0.5. The expected value of the utility is in fact, -3.8, which we call EMV for the expectation of the mean value solution. The other common approach is to find the optimal decision under each of the future scenarios. This would be the strategy if we could postpone our decision or knew the future with certainty. This perfect information (or, in stochastic programming, following Madansky [16] the wait-and-see solution (WS)) is to invest in whatever has the highest yield in each period. In this case, we would invest in stocks if stocks increase 25% in a five year period (bonds increase 14%) and we would invest in bonds if bonds increase 12% (stocks increase 6%). Thus, with probability 0.125, we receive a return of (1.25)3 = 1.953, with probability 0.125, we receive a return of (1.12)3 = 1.405, with probability 0.375, we receive a return of 1.12 * (1.25)2 = 1.75, and, with probability 0.375, we receive a return of (1.12)2 * 1.25 = 1.568. The result is that we would have an expected utility of WS = 10.5. It is quite difficult to imagine how this analysis can be used however. The WS solution invests everything in stock or bonds and never splits the investments in any period. Now, let us consider a formulation that considers the uncertainty explicitly in a single mathematical programming formulation. We have two alternative methods for writing the formulation in general. They correspond either to taking each outcome in each period separately or to model the scenarios more explicitly. We describe the general forms of these formulations denoting the random return by r(k, t) = r(k, t, w) where w is some underlying. random element in 0. The decisions on investments are random as well. We describe these decisions as x(k, t) = x(k, t, w). From the randomness of the returns and investment decisions, our final wealth is also a random variable W = W(w). A key point about this investment model is that we cannot completely observe the random element w when we make all of our decisions x(k, t, w). We can only observe the returns that have already taken place. In stochastic programming, we say that we cannot anticipate every possible outcome so that our decisions are nonanticipative of future outcomes. Before the first period, this restriction corresponds to saying that we must make fixed investments, x(k, 1), for all w E Q2, the space of all random elements. In the next period, we suppose that the random elements w correspond to N1 different possibilities for outcomes in the first investment period. We can therefore partition Q into Q1,..., 1 corresponding to 4

these different initial outcomes. Decisions for a given value of w must be the same for every w within the set. We can therefore describe our second period decisions just in terms of the Q1 that occurs in the first period. We write these decision variables as x(k, 2, i), where i = 1,..., N1. We can continue this process by defining.tl as the set of all w that correspond to outcomes ij in periods j = 1,...,t. We can then describe the nonanticipative decisions as x(k, t + 1, ii,..., it), which depend on the outcomes r(t, ii,..., it). In the following, for simplicity, we assume that each set of outcomes ii,..., it-1 up to time t-1 leads to Nt outcomes at time t. In all T periods, we would then have N1 -N2... NT different possible outcomes. To illustrate how quickly these problems can grow, note that, with just ten outcomes per period, we would obtain 1010 outcomes in 10 periods. We need to attach probabilities to all outcomes. We let the probability of the ith outcome in period t given outcomes ij in periods j = 1,...,t - 1 be p(t,il,...,it). Note that we must have tlp(t, il,..., it, i) = 1 for all t and i,..., itl. We then can state a general formulation for our problem. We wish to find max z = Ei, i p(T *,,, iT) -qs(ii,..., iT)) s. t. KL x(k, 1) = E1 r(k, t, il., it-1)x(k, t-1,il..., it-2) -E= x(k, t, il *, it-1) = 0, for all (i1,..., i ), t = 2,...,T EK, 1 (2) -v(i,...,iT) + s(i,..,iT) = G for all 1 < it < Nt; 1 < k < K; 1< t, T. where v(il,..., i) represents any amount above the goal and s(i,..., iT) represents any shortfall from the target value G. With the data given above, each period has two new alternative outcomes, so Nt = 2 for t = 1, 2, 3.

Each p(i1, i2, is) is 0.125. The resulting specification of (2) is: max = E, =1 E2 = Eis=l 0.125(v(il, i2, is) -4s(i, 2, i3)) s. t. x(1, 1) + x(2, 1) = 55, -1.25x(1, 1) - 1.14x(1, 2) + x(1, 2, 1) + x(2,2, 1) = 0, -1.06x(1, 1) - 1.12x(1, 2) + x(1, 2,2) + x(2,2, 2) = 0, -1.25x(1, 2, 1) - 1.14x(2, 2,1) + x(1, 3,1,1) + x(2, 3,1,1) = 0, -1.06x(1, 2,1) - 1.12x(2,2,1) + x(1, 3,1,2) + x(2, 3,1,2) = 0, -1.25x(1, 2, 2) - 1.14x(2, 2,2) + x(1, 3,2,1) + x(2, 3, 2,1) = 0, -1.06x(1, 2, 2) - 1.12x(2, 2,2) + x(1, 3, 1, 2) + x(2, 3, 1, 2) = 0, 1.25x(1, 3,1,1) + 1.14x(2,3,1,1) - v(1,1,1) + s(1,1,1) = 80, 1.06x(1, 3,1,1)+ 1.12x(2,3,1,1) - v(1, 1,2)+ s( 1,1,2) =80, 1.25x(1, 3,1,2) + 1.14x(2,3,1,2) - v(1, 2,1) + s(1, 2,1) = 80, 1.06x(1, 3, 1, 1)+ 1.12x(2,3,1,2) - v(1, 2,2) + s(1, 2, 2) =80, 1.25x(1, 3,2, 1) + 1.14x(2, 3,2, 1) - v(2, 1, 1) + s(2, 1, 1) = 80, 1.06x(1, 3,2, 1) + 1.12x(2,3, 2, 1) - v(2,1,2) + s(2, 1, 2) = 80, 1.25x(1, 3,2,2) + 1.14x(2,3,2,2) - v(2,2, 1) + s(2,2, 1) = 80, 1.06x(1, 3,2,2) + 1.12x(2, 3,2,2) - v(2, 2,2) + s(2, 2, 2) = 80, x(k, t, il,..., it-l) > 0,v(il, i2, i3) > 0 s(il, i2, i3) 0, for all k,t, i, i2, i3. Another approach to multistage problems is to consider decisions as dependent on the full horizon scenarios, a. We then substitute a scenario set S for the random elements PQ. Probabilities, p(a), returns, r(k, t, a), and investments x(k, t, a) become functions of the T-period scenarios. We must still maintain nonanticipativity, but this time we do so explicitly in the formulation via constraints. First, the scenarios that correspond to the same set of past outcomes at each period form groups, Sl...,tl, for scenarios at time t. Now, all actions up to time t must be the same within a group. We do this through an explicit constraint. The new formulation of (2.1) becomes: max z = a p(a)(iv(a) - qs(a)) s. t. k=l x(k, 1, a) = w,Va E S; Ek= r(k, t, a)x(k, t - 1, a) - x(k, t, a) = 0,a E; t = 2,...,T; k=l r(k, T, a)x(k, T, a) -v(a) + s(a) =G; (4) (C'es;(,) p(a')x(k, t, a')) -('eS(t p(a'))x(k, t, a) =,V1 <k < K; V1 < t < T;Va E S; x(k, t, a) > O, v(a) > 0, s(a) > 0; V1 < k < K; V1 < t < T; Va E S; where I(a,t) = {il,..., it-} such that a E St Note that the last equality constraint indeed forces all decisions within the same group at time t to be the same. We use the form above because it represents a projection constraint useful in certain methods (see, e.g., [17]). Formulation 4 has a special advantage for the problem here because these nonanticipativity constraints are the only constraints linking the separate 6

scenarios. Without them, the problem would decompose into a separate problem for each a, maintaining the structure of that problem. For our problem, we have again two outcomes in each period and three periods. In terms of formulation (4), we have jSI = 8 scenarios. This yields probabilities p(a) = 0.125 for each scenario a. The returns are r(l,t, a) = 1.25,r(2,t,a) = 1.14 for t = 1,a = 1,...,4, fort = 2,a = 1,2,5,6, and for t = 3, a = 1,3,5,7. In the other cases, r(1, t, a) = 1.06, r(2, t, a) = 1.12. Formulation 4 becomes max z = =1 0.125(iv(a) - qs(a)) s. t. x(, 1, a) + x(2, 1, a) = 55, a = 1,...,8; -1.25x(1, 1,a)- 1.14x(2,, a) +x(1,2, a) + x(2, 2, a) = 0, a = 1,...,4; -1.06x(1, 1,a)- 1.12x(2, 1, a) +x(1,2, a) + x(2, 2, a) = O, a = 5,...,8; -1.25x(1, 2, a) - 1.14x(2, 2, a) +x(1, 3, a) + x(2, 3, a) = 0, a = 1,2,5,6; -1.06x(1, 2, a) - 1.12x(2, 2, a) +x(1, 3, a) + x(2, 3, a) = Oa = 3,4, 7,8; 1.25x(1, 2, a) + 1.14x(2,2, a) +v(la) - s(a) = 80, a = 1,3,5,7; 1.06x(1, 2, a) + 1.12x(2,2, a) +v(la)- s(a) = 80, la = 2,4,6,8; (E ~1 0.125x(k, 1, a,)) -x(k,1, a) = O. k = 1, 2; a = 1,....,8; (5) (E4=1 0.125z(k, 2, a)) -0.5x(k, 1, a) = 0, k = 1,2; a = 1,...,4; (Es85 0.125x(k, 2, a)) -0.5x(k, 1,a) = 0, k = 1,2; a = 5,...,8; (E=1 0. 125x(k, 2, a)) -0.25(k, 3, a) =, k= 1,2; = 1,2; (E=3 0.125x(k, 2, a)) -0.25x(k, 1, a) = 0, k = 1, 2; a = 3, 4; (E2=5 0.125x(k, 2, a)) -0.25x(k, 3, a) =,k= 1, 2; a = 5,6; (E8=7 0.125(k, 2, a)) -0.25x(k, 1, a) = 0, k = 1, 2; a = 7, 8; x(k, t, a) > 0, v(a) >, s(a) > 0; k= 1,2; t = 1,3; a = 1,...,8. In modeling terms, the nonanticipativity constraint makes it relatively easy to move from a deterministic model to a stochastic model of the same problem. The addition of the scenario indicators and nonanticipativity constraints are the only additions to a deterministic model. Given the ease of this modeling effort, standard optimization procedures can be simply applied to this problem. However, as we noted above, the number of scenarios can become extremely large. The model in (5) also has more constraints than (4) to compensate for a loosening of the restrictions among secnarios with similar pasts. Standard methods may not be able to solve the problem in any reasonable fashion, necessitating other techniques. In this financial problem, it is particularly worthwhile to try to exploit the underlying structure of the problem without the nonanticipativity constraints. This relaxed problem is in fact a generalized network that allows the use of efficient network techniques (see Mulvey and Vladimirou [17]). With either formulation (2-3) or (4-5), in completing the model, some decisions must be made about the possible set of outcomes or scenarios and the coarseness of the period structure, i.e., the number of periods T allowed for investments. We must also find probabilities to attach to outcomes within each of these periods. These probabilities are often approximations (see Birge and Wets [4] and Kall, Ruszczyniski 7

and Frauendorfer [12]). A key observation is that the important step is to include stochastic elements at least approximately and that deterministic solutions will most often give misleading results. Solving the problem in (5) with these parameter values yields an optimal expected utility value of -1.52. We will call this value, RP, for the expected recourse problem solution value. The optimal solution (in thousands of dollars) appears in Table 1. Period, Scenario Stocks Bonds 1,1-8 41.5 13.5 2,1-4 65.1 2.17 2,5-8 36.7 22.4 3,1-2 83.8 0.0 3,3-4 0.0 71.4 3,5-6 0.0 71.4 3,7-8 64.0 0.0 Scenario Above G (v) Below G (s) 1 24.8 0.0 2 8.87 0.0 3 1.42 0.0 4 0.0 0.0 5 1.42 0.0 6 0.0 0.0 7 0.0 0.0 8 0.0 12.2 Table 1. Optimal solution with 3-period stochastic program. In this solution, the initial investment is heavily in stocks ($41,500) with only $13,500 in the government securities. Notice the reaction to first period outcomes however. In the case of scenarios 1-4, stocks are even more prominent while scenarios 5-8 reflect a more conservative bond portfolio. In the last period, notice how the investments are either completely in stocks or completely in bonds. This is a general trait of one-period decisions. The optimization leads to an extreme point in which only one type of investment is made. The main advantage of the multiperiod stochastic formulation is indeed to enable a hedging solution involving multiple investment types. The solution in Table I shows only stock investment in scenarios 1,2, because there is no risk of missing the target. In scenarios 3-6, stock investments may cause one to miss the target so they are avoided. In scenarios 7,8, the only hope of reaching the target is through stocks. The stock investment is, therefore, not 8

a monotonic function of wealth. The general observation is that any monotonic decision rule based on the current state is suboptimal. We compare the results in Table 1 to the deterministic model. There, we would realize an expected utility of EMV = -3.84, while the stochastic program value, RP = -1.52. The difference between these quantities is the value of the stochastic solution ( introduced in Birge [1]), VSS = RP - EMV = -1.52 - (-3.84) = 2.32. Another comparison is in terms of the probability of reaching of the goal. Models with these types of objectives are called chance-constrained programs or programs with probabilistic constraints (see Charnes and Cooper [5] and Prekopa [19]). Notice that the stochastic program solution reaches the goal 87.5% of the time while the mean value solution only reaches goal 50% of the time. In this case, the value of the stochastic solution is even more significant. Some distinction should be made between the value of the stochastic solution and the expected value of perfect information, which compares the recourse problem value (or maximum expected utility, RP) to the expectation of scenario solution values that would be obtained if the future was known perfectly. Here, the expected value of perfect information is EVPI = WS - RP = 10.5 - (-1.52) = 12.0. In this case, EVPI > VSS, but in many cases (see Birge [1]), we may have VSS > EVPI. In fact, since WS > RP > EMV, VSS and EVPI are only assured of being the same when WS = EMV. Either could be zero, while the other is positive. Another option in practice is to formulate a simpler model by limiting the horizon. This may seem quite reasonable since indeed we are only interested now in the first period decision. Consider then a two-period, 10-year model. In this case, we need to determine conditions on the end of the horizon to make our shorter time horizon model reflect the original model as closely as possible. This is the problem of mitigating end effects (see Grinold [10]). It seems reasonable here to choose a target value that will ensure our achieving the original $80,000 target value at year 15. We, therefore, make our 10-year target equal to $71,400. Solving this two-period, 10-year problem with all other data as in the original 3-period model, we obtain the optimal solution in Table 2. Notice how different the 10-year solution is from the 15-year solution. We now predominantly invest in bonds in the first period because we have not fully considered the chances of recovering later from initial poor stocks investments. In this case in five years, with probability one half we have $63,800, and, with 9

Period, Scenario Stocks Govt Secs 1,1-4 9.8 45.2 2,1-2 0.0 63.8 2,3-4 17.1 44.0 Scenario Above G Below G 1 1.28 0.0 2 0.0 0.0 3 0.0 0.0 4 0.0 4.12 Table 2. Optimal solution with 2-period, 10-year stochastic program. probability one half, we have $61,100. Again, we may solve the model with two five-year periods from these wealth levels. The result is an expected utility of 1.87 in the first case and -5.77 in the second case. The overall expected utility is -3.9. This expected utility is quite close to that obtained by the completely deterministic model. It demonstrates the importance of the horizon. In general, the middle period in the first stochastic programming model is useful because it allows for a type of steady-state or turnpike policy (see Birge and Dempster [3]) while the first and last periods have start-up or shut-down characteristics. It is, therefore, often prudent to have at least a three-period model for dynamic decision making. In closing this section, note that the mathematical form of thatis problem actually represents a broad class of control problems. In fact, it is basically equivalent to any control problem governed by a linear system of differential or difference equations. We have merely taken a discrete time approach to this problem. The approach can be applied to the control of a wide variety of electrical, mechanical, chemical, and economic systems. We merely redefine state variables (now,wealth) in each time period and the controls (investment levels). The random gain or loss is reflected in the return coefficients. Typically, these types of control problems would have nonlinear (e.g., quadratic) costs associated with the control in each time period. This presents no complication for our purposes, so we may include any of these problems as potential applications. In this problem, we had a limited set of possible outcomes in each period. In practical problems, we could not expect such a small finite set of realizations. One of the main steps in stochastic program modeling is how to select such sets of scenarios and how to compare their use with what may actually happen. One goal is to create approximations with a small number of realizations that bound the expected objective value from above and below (see Birge and Wets [4]). Another goal may be to obtain asumptotic convergence through sampling (see Dantzig and Glynn [7], Ermoliev [8], and HIgle and Sen [11]). 10

In this model, we were able to model the utility with a piecewise linear function to obtain a linear program. This form allows very large-scale computations (see Wets [22]) and can lead to great efficiencies over standard linear programming techniques (see Birge [2] and Gassmann [9]). Linear programming structure is not, however, necessary in stochastic programs. The example in the next section demonstrates this quite explicitly. Section 4. Design for Manufacturing Quality This section illustrates a common engineering design problem that we model as a stochastic program. The problem demonstrates nonlinear functions in stochastic programming and provides further evidence of the importance of the stochastic solution. Consider a designer deciding various product specifications to achieve some measure of product cost and performance. The specifications do not, however, completely determine the characteristics of each manufactured product. Key characteristics of the product are often random. For example, every item includes variations due to machining or other processing. Each consumer also does not use the product in the same way. Cost and performance characteristics thus become random variables. Deterministic methods may yield costly results that are only discovered after production has begun. From this experience, designing for quality and consideration of variable outcomes has become an increasingly important aspect of modern manufacturing (see, for example,. Taguchi, Alsayed, and Hsiang [21]). In this development, the methods of Taguchi have been widely used (see also Taguchi [20]). These approaches can, in fact, be seen as examples of stochastic programming, although they are not often described this way. In this section, we give a small example of the uses of stochastic programming in manufacturing design and show how the general stochastic programming approach can be applied. We note that we base our analysis on actual performance measures (or predictions) whereas the Taguchi methods generally attach surrogate penalties to deviations from nominal parameter values. We consider the design of a simple axle assembly for a bicycle cart. The axle has the general appearance in Figure 2. The designer must determine the specified length I and diameter d of the axle. We use inches to measure these quantities and assume that other dimensions are fixed. Together, these quantities determine the performance characteristics of the product. The goal is to determine a combination that will give the greatest expected profit. The initial costs are for manufacturing. We assume that a single process is used. No alternative 11

LI 4 Figure 2. An axle of length 1, diameter d, with a central load P. technologies are available, although, in practice, several processes might be available. When the product is produced, the actual dimensions are not exactly those that are specified. For our example, we suppose that the length I can be produced exactly but that the diameter d is a random variable, d(d), that depends on a specified mean value or machine setting, d. We assume a triangular distribution for d(d) on [0.9d, l.ld]. This distribution has a density, {- (d - 0.9d) if 0.9d < d < d; fd (d) = (6o f(d)-= d2(1.1d-d) if d<d<l.ld (6) 0 otherwise. The decision is then to determine 1 and d, subject to certain limits, I < Im"x and d < d"a, in order to maximize expected profits. For revenues, we assume that, if the product is profitable, we sell as many as we can produce. This amount is fixed by labor and equipment regardless of the size of the axle. We, therefore, only wish to determine the maximum selling price that generates enough demand for all production. From marketing studies, we determine that this maximum selling price depends on the length, and is expressed as s(l-e-~01), (7) where s is a maximum possible for any such product. Our production costs for labor and equipment are assumed fixed, so that only material cost is variable. This cost is proportional to the mean values of the specified dimensions since material is acquired before the actual machining process and producing many units leads to low unit material cost variance. For c, the cost of a single axle material unit, the total manufacturing cost for an item is then c( ). (8) In this simplified model, we assume that no quantity discounts apply in the production process. 12

Other costs are incurred after the product is made due to warranty claims and potential future sales losses from product defects. These costs are often called quality losses. In stochastic programming terms, these are the recourse costs. Here, the product may perform poorly if the axle becomes bent or broken due to excess stress or deflection. The stress limit, assuming a steel axle and 100 pound maximum central load, is: < 39.27. (9) For deflection, we use a maximum 2000 rpm speed to obtain: I3 d < 63169. (10) When either of these constraints is violated, the axle deforms. The expected cost for not meeting these constraints is assumed proportional to the square of the violation. We express it as Q(, d, d):=min{wy2 s. t. - -y < 39.27, - 300y < 63169}, (11) where y is, therefore, the maximum of stress violation and (to maintain similar units) 3 of the deflection violation. The expected cost, given I and d, is then: Q(l, d) = Q(l, d, d)fd(d)dd, (12) Jd which can be written as: =w l.ld _1 13 Q(l, d) =w (100/2) mind-.9d, 1.1-d}[max0, ( )- 39.27,(30d )-210.36}]2dd. (13) J.9d d3 300d4 The overall problem is to find: max (total revenue per item - manufacturing cost per item - expected future cost per item). (14) Mathematically, we write this as: max z(, d) = s(l - e-0l11) - c( ) -Q(ld)) 4 (15) s. t. 0 < <, max dmax. In stochastic programming terms, this formulation gives the deterministic equivalent problem to the stochastic program for minimizing the current value (include risk) for the design decision plus future reactions 13

to deviations in the axle diameter. Standard optimization procedures can be used to solve this problem. Assuming maximum values of 1max = 35, dmax = 1.25, a maximum sales price of $10 (s = 10), a material cost of $0.025 per cubic inch (c =.025), and a unit penalty w = 1, an optimal solution is found at I* = 33.6, d* = 1.038, and z* = z(l*,d*) = 8.94. In this solution, the stress constraint is only violated when.9d= 0.934 < d < 0.949 = (1/39.27)1/3. We again consider the expected value problem where random variables are replaced with their means to obtain a deterministic problem. For this problem, we would obtain: max zDet(, d) = s(1 - e-0.) - c( 4 )-[max{O, (d) - 39.27, (300)- 210.36}12 1) - c(~4 c T 3O0d4 (16) s. t. 0 < I< Lmax,0 o d < dmax. Using the same data as above, an optimal solution to (16) is 1Det = 35.0719, dDet = 0.963, and ZDet(lDet, dDet) = 9.07. In this case, the deterministic solution makes the stress constraint active. Again, any deterministic model pushes the solution again one of the constraints. The result is that any randomness leads to frequent constraint violations and warranty or quality costs. At first glance, it appears that this solution obtains a better expected profit than the stochastic problem solution. However, this deterministic problem again paints an overly optimistic picture of the actual situation. The deterministic objective is (in the case of concave maximization) always an overestimate of the actual expected profit. As is often observed in practice, prediction based on mean value optimization problems are always biased. In this case, the true expected value of the deterministic solution is Z(1Det, dDet) = 5.88. This problem then has a value of the stochastic solution equal to the difference between the expected value of the stochastic solution and the expected value of the deterministic solution, z* - z(lDet, dDet) = 3.06. In other words, solving the stochastic program yields an expected profit increase of j. = 52% over solving the deterministic problem. This problem is another example of how stochastic programming can be used. It has nonlinear functions and a future penalty cost on constraint violation, called simple recourse structure. In other problems, decisions may also be taken after the observation of the outcome to reduce this penalty. For example, we could inspect and then decide whether to sell the product. This often leads to tolerance settings and is indeed the focus of much of quality control. The general stochastic program provides a framework for uniting design and quality control. Many loss functions can be used to measure performance degradation to help improve designs in their initial stages. These functions may include the stress performance here, the Taguchi-type of quadratic loss, or methods based on reliability characterizations. 14

Most traditional approaches assume some form for the distribution as we have done here. This situation rarely matches practice, however. Approximations can nevertheless be used that obtain bounds on the actual solution value so that robust decisions may be made without complete distributional information. 5. Conclusions This paper presented a brief discussion of stochastic programming models. We began with a simple example in financial planning that illustrated the value of the stochastic solution over that of a deterministic model solution. We also showed how this quantity is different from the expected value of perfect information and noted how the model could take advantage of linear programming methods. We then described a problem with highly nonlinear functions as an example of using stochastic programming for designing to meet quality goals. In this example, we also demonstrated the value of the stochastic solution. As the other chapters in this volume indicate, there are many other example of stochastic programming formulations. We should mention the extensive work in energy and power planning (see Dantzig and Glynn [6], Louveaux [15], and Noel and Smeers [18]) as just one additional example. Several other references appear in the survey by King [14]. Many more applications are open to stochastic programming as powerful new solution and modeling techniques become increasingly available. References 1. J.R. Birge, "The value of the stochastic solution in stochastic linear programs with fixed recourse," Mathematical Programming 24 (1982) 314-325. 2. J.R. Birge, "Decomposition and partitioning methods for multi-stage stochastic linear programs," Operations Research 33 (1985) 989-1007. 3. J.R. Birge and M.A.H. Dempster, "Optimality conditions for match-up strategies in stochastic scheduling," Technical Report 92-58, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1992. 4. J.R. Birge and R. J-B. Wets," Designing approximation schemes for stochastic optimization problems, in particular, for stochastic programs with recourse," Math. Progr. Study 27 (1986) 54-102. 5. A. Charnes and W. W. Cooper, "Chance-constrained programming," Management Science 5 (1959) 73-79. 15

6. G.B. Dantzig and P. Glynn, eds., Resource Planning under Uncertainty for Electric Power Sytems (National Science Foundation, Washington, DC, 1989). 7. G.B. Dantzig and P. Glynn, "Parallel processors for planning under uncertainty,"Annals of Operations Research 22 (1990) 1-21. 8. Y. Ermoliev, "Stochastic quasigradient methods and their applications to systems optimization," Stochastics 9 (1983), 1-36. 9. H. I. Gassmann, " MSLiP: A computer code for the multistage stochastic linear porgramming problem," Mathematical Programming 47 (1990) 407-423. 10. R.C. Grinold, "Model building techniques for the correction of end effects in multistage convex programs, Operations Research 31 (1983) 407-431. 11. J. Higle and S. Sen, "Stochastic decomposition: an algorithm for two stage linear programs with recourse,", Math. of O.R. 16 (1991) 650-669. 12. P. Kall, A. Ruszczyriski, and K. Frauendorfer, "Approximations in stochastic programming," in: Y. Ermoliev, R. Wets, eds., Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 33-64. 13. J. G. Kallberg and W.T. Ziemba, "Comparison of alternative utility function sin protfolio selection problems, Management Science 29 (1983) 1257-1276. 14. A. King, "Stochastic programming problems: examples from the literature," in: Y. Ermoliev, R. Wets, eds., Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 543-567. 15. F. V. Louveaux, "A solution method for multistage stochastic programs with recourse with application to an energy investment problem," Operations Research 28 (1980) 889-902. 16. A. Madansky, "Inequalities for stochastic linear programming problems," Management Science 6 (1960) 197-204. 17. J. Mulvey and H. Vladimirou, "Stochastic network optimization models for investment planning," Annals of Operations Research 20 (1989) 187-217. 18. M.-C. Noel and Y. Smeers, "Nested decomposition of multistage nonlinear programs with recourse," Math. Program. 37 (1987) 131-152. 19. A. Prekopa, "Numerical solution of probabilistic constrained programming problems," in: Y. Ermoliev, R. Wets, eds., Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 123-140. 16

20. G. Taguchi, Introduction to Quality Engineering (Asian Productivity Center, Tokyo, 1986). 21. G. Taguchi, E. A. Alsayed, T. Hsiang, Quality Engineering in Production Systems (McGraw-Hill, New York, 1989). 22. R. Wets, "Large-scale linear programming techniques in stochastic programming," in: Y. Ermoliev, R. Wets, eds., Numerical Techniques for Stochastic Optimization, Springer, Berlin, 1988. 23. S.A. Zenios, ed. Financial Optimization (Cambridge University Press, Cambridge, 1992). 24. W. T. Ziemba and R.G. Vickson, eds., Stochastic Optimization Models in Finance (Academic Press, New York, 1975). 17