An Upper Bound on the Network Recourse Function1 Christopher J. Donohue and John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor MI 48109-2117 Technical Report 95-5

An Upper Bound on the Network Recourse FunctionI Department Christopher J. Donohue of Industrial and Operations University of Michigan Ann Arbor, Michigan 48109 Engineering Department John R. Birge of Industrial and Operations University of Michigan Ann Arbor, Michigan 48109 Engineering.Ahstra ci: Tis paper considers netIwork flow problems in which the link upper capacities are independetlelt (listributed random variabtles. The opt imial objective value is then a non-increasing. collivex fulction of these random capacities. This function is known as the network recourse function for two-stage stochastic programs in which tihe second stage is a pure network flow problem. Thiis paper exploits the network structure to show that tilis function also has a property called convex marginal return functions with resplect.to tipper c)apacities of links with a common initial or termiinal node. This results in the ability to (establish ait tipper bound on the expected value of tlhe optimal objective value which only considers high and low extreme values for upper capacities of links with common initial or terminal nod(es. This often significantly decreases the function evaltuations needed, and still provides an effective bound. sKxperimental results are given. rTilis work has been partially supported by the National Science Foundation under Grant DDM-9215921 and the Great Lakes Center for Trucking and Transit Research.

1 Introduction The classic two-stage stochastic program with recourse (see Dantzig [7], Walkup and Wets [15]) is the problem of finding a first-stage decision which is heavily influenced by uncertainty in the second stage. Second-stage decisions, or recourse actions, are taken after the uncertain second-stage problem parameters are known with certainty. The goal is to choose a first stage decision which minimizes the cost incurred in the first stage plus the expected costs incurred in the second period, given the first stage decision. Solving for the expected costs in the second period, also known as the expected value of the recourse function, can be difficult. Decomposition methods are effective for stochastic programs since large stochastic programs can be partitioned into much smaller individual scenarios or subproblems (see Van Slyke and Wets [14], Birge [2]). Further, decomposition methods allow straightforward use of parallel computing which can yield sigtlificant computational benefits (see Birge et. al [3]). Exploiting specific structure of second-stage problems is another means for overcoming the difficulty wit l finding t le expected value of the recourse function. In stochastic programs in which the second stage pIrolblem l i. a plure lnetwork flow problem, the second stage problem is called the network recourse function. Wallace [16] considered such stochastic programs and developed computationally effective methods for solving large Illmblers of networks which differ only by lodle supplies and demands. 'Ile probleml of solving for the expected value of t lie recourse function, however, becomes overvhelming wvhen t hle number of possible realizations of the random variables is large. For general stochastic programs,, effect ive approximnation methods exist whichl allow flirt her simplification (see Birge and Wets [5]). Further, sIpecific bounds for the network recourse function lhave been studied. Wallace [17] developed an upper bound for thie network recourse function which is found by solving 1

three separate minimum cost network flow problems, regardless of the number of random elements. Frantzeskakis and Powell [9] and Cheung and Powell [6] developed lower bounds for multistage stochastic networks which are based upon linear approximations and convex approximations, respectively. Both bounds use backward recursion and were successfully applied to dynamic vehicle allocation problems in which some links have stochastic upper bounds. In this paper, the network recourse function is considered for stochastic programs in which each of the second stage problems is a pure minimum cost network flow problem differing only by the link upper capacities. We consider second-stage problems in which the number of random elements is large and the random elements are independent, in some cases giving a practically infinite number of scenarios. One stage of the dynamic vehicle allocation problem in which a fleet carrier must route vehicles according to the (lemands of many independent customers is an example of such a problem. This problem, as well as applroximlatioin mlethods, are discussed extensively in [6] and [9]. Ill tlis paper, an new effective and efficient upper bound is developed for the expected value of the network recourse function. Section 2 gives a mathemnatical formulation of a stochastic minimum cost network flow prol)leml. We then show that. the network recourse function, when viewed as a function of the random capacities, is a non-increasing convex funiction with a property called convex marginal return functions with respect to upper capacities of links havilng either a common initial node or a common terilinal Ilode. Th1ese properties are the1n used to finld an1 effective upper bound on the expected value of tlhe network recourse function which does not re(luire prohibitive amounts of computation. In the final sectionl thllese bounds are applied to several inetwork prob)lells to demonstrate their effectiveness. 2

2 Formulation of a Stochastic Minimum Cost Network Flow Problem Consider a directed network G, consisting of a set of nodes X = 1, 2,..., m and a set of directed links A joining various pairs of nodes in KA. For any link (i, j) E A, node i is the initial node of (i, j) and node j is the terminal node of (i, j). The goal of the program is to route a given supply of a commodity from specified sources, denoted S C Air, to specified sinks, denoted T C A, at minimum cost. Each node i in S has an amount bi > 0 of the commodity available at that source. Each node i in T has an amount b () of the commodity that must be routed to that sink i. The cost of routing each unit along link (i, j) in A is cij. Finally, each directed link (ij) in A has lower and upper capacity constraints, lj and uij respectively, on the amount of flow that can be sent along that link. Throughout this paper, the upper capacities uj are assumed to be stochastic, governed by the independent, non-negative, discrete random variables o,9. Let jij denote the flow along link (ij). Then, the problem can be viewed as a function of the stochastic upper capacities. oij as follows: f(o)= -rin Z (i,j IEA Cij i3 6b; if iC S subject to: ij )EA X - LJ iEA u)J = ' 0 if i A \ (S U T) -bi if i E T lj < uj=<-K V(i,j)eA. _ij > (lZij V (ij)A The problem can easily be transformed to a circulatory network flow problem by creating a super 3

source node s, a super-sink node t, links (s. i) for each i G S with upper and lower capacity bi, links (j.t) for each j E T with upper and lower capacity bj, and a link (t,s) with upper and lower capacity iE. bi = EjET bj. The cost per unit flow on all these links is zero. Let Ah* = ArU{s, t and A' = A U{(s, i)Vi E 5, (j, t)Vj E T, (t. s)}. Then the problem can be rewritten as follows: f(o) = Min E(i,j)A Cijij subject to: (ij)EA. Xij - E(j,i)EA Xi = 0 Vi E V' ( xij ~ Uij = ij ii > lij The applications of minimum cost. flow problems are vast (see, e.g., Bazaara, Jarvis and Sherali [1], \lurty [12]). Any such problem which is governed by demand for commodity movement may be viewed as a stochastic m11inimum cost network flow problem. For applications of this tvype of problem, see [13]. [16]. 3 Properties of the Network Recourse Function Thle functionl f(o) has several properties whlich cian 1w( expl)loited to make approximations easier ald ioore effective. First. the problem is a stochastic lilear programl. Thus, f(~) is a piecewise linear, convex filnction illn (see. e.g., Birge and Louveaux [11). Fulrtlher, since anv routing which is possible for ol is also possible for 02 > 1, it is readily seen that f(o) is a non-increasing function of d. The next property to show needs to be defilnedl first. 4

Definition: A function f(dl,..., dn) is said to have convex marginal return functions with respect to di and dj, 1 < i < j < n, if, for all A > 0, > 0, f(d...di + A,.....,dj dn) - f(di,..., di,..., dj +,...,d) > f(di di +,...,dj.....,d)-f(d,...,di,...,dj,... dn). The remainder of this section shows that f(o) has convex marginal return functions with respect to upper capacities of links having either commom initial nodes or common terminal nodes. Briefly, the explanation for convex marginal return functions is as follows. Consider a network flow problem in which Link 1 and Link 2 have the same initial node. Suppose that thle inetwoork flow problem is solved for particular values of 1 and o2, the upper capacities for Link 1 and Link 2. respectively. Now increase the value of oi by one, while leaving all other capacities unchanged. Su;ppose that the new problem is solved by a network algorithm such as the out-of-kilter method which reciisivel1 deletes negative cost cycles, and the solution to the previous problem is used as the starting sollitioll. Tihe only possible negative cost cycle would have to include an increase of flow on Link 1. since the pirevious solution wvas optimal aiid the only changed aspect of the problem is the upper capacity of Link 1. But that implies that the solution to the updated problem must either decrease or leave nclIhaiied tlie flow along Link 2. In eitlher evenit. if o- i- Inow increased by one, the effect of that increase is omiilg to he less than if O, had been ilicreasedl b)ffore ol. A similar argument can be used if Link 1 and Link 2 have tlie same terminal node. Now in order to prove this property rigorotusly. thi opt imality conditions and the basic ideas behind tlie 0 Ol-of-Ai lter Algorithm need to be reviewed.

Let the dual variables from program (1) be defined as: /1t - dual variable corresponding to conservation of flow constraint (1) at, node i, i e A,', Aij dual variable corresponding to lower capacity constraint (3) on link (i,j),V(i,j) E A* ij dual variable corresponding to upper capacity constraint (2) on link (i,j),V(i,j) E A* Then, examining the complimentary slackness conditions for this problem gives the following result for all minimum cost network flow problems (see, e.g., Bazaara, Jarvis and Sherali [1]). Thleorem 3.1 Let x be any conserving flow, and let p be any integral vector. Then x and pL are respectively primal and dual optimal solutions to program (1) if and only if for all (i,j) in A*, Cij - ~i + 1Pj > 0 implies Xij = lij Cij - i -+.j < 0 implies xij = uij cij - Pi + Pj = 0 implies lij < Xij < uij. Proof: See Fulkerson [10]. tiilkersolt [10] used this theorem to (levelop the Oul-of-Kilter MIethod for solving minimum cost network flow problems. A link (i,j) wllich satisfies the conditions of Theorem 3.1 is said to be il-kilter. wllile those which do not satisfy' those conditions are out-of-kilter. Each link is given a kilter number, N which corresponds to the minimal change of flow requliredl to bring that link into kilter; clearly, in-kilter links have a kilter number of zero. Tle goal of the algorithm is to have te st ie stm of all kilter inumbers equal zero. The method accomplishes tis by successively canceling negative cost resi(lual cycles. A link (i,j) is selected from among those lilks which are currently out-of-kilter. If flow nieeds to be increased along (i,j), then node j is labeled. If flow needs to be decreased, node i is labeled. 'The method then proceeds to look from labeled nodes 6

to see if flow along links to adjacent nodes can be increased or decreased, as appropriate. The labels generally contain information about the direction of flow change through that node and tiLe maximum change possible through that node. While all out-of-kilter links are allowed to have flow changes (which will bring them closer to being in-kilier), only in-killer links for which pi - lj - cij = 0 are allowed to have flow change. The labeling continues until either a circuit is found which includes link (i,j) or no more nodes can be labeled. In the latter case, a dual variable change is made in which the dual variables, pk, for all labeled nodes are increased by an equal amount. This step allows for more labeling to be done in the next labeling step, or to determine that the problem is infeasible. In the former case, a flow change is made in which the flow along (i. j) is changed. In either case, the kilter number of each link either remains the same or strictly decreases. The kilter numbers never increase. In any labeling step, let X denote the set of labeled nodes, and let X denote the set of unlabeled nodes. For a full description of the method, see Fulkerson [10]. Bazaara, Jarvis &- Sherali [1], or 'Murty [12]. One insightful point to make about network flows in general and, in particular, the Out-of-AKiller A\lgorit lili. is the following restatement of the objective function, which will be used later. If the matrix L is used to denote the node-arc incidence matrix, then any conserving flow satisfies Ex = O. and so /lJ-_'x = 0. lThis implies that for a conserving flow which satisfies the lower and upper capacity constraints. lite ob)ject ive function can be written: f(x') = c, (,j iEA~ = E (C', - / + ij)xzj. (2) (ij )EA' 'Ilie (c3 - /1 + p) used in Equation (2) is exactly the equation used in Theorem 3.1 to determine if link

(i,j) is in-kilter or not. Another point to note is the inability to increase flow along certain links during certain primal flow changes. As mentioned, the Out-of-Killer Algorithm works by cancelling all negative cost residual cycles. Suppose a particular network is solved, then some Link k has its upper capacity increased by one. Since the previous problem had been solved, all kilter numbers were zero exactly. Now the only possible nonzero kilter number is that of Link k. Its only possible nonzero value is one. Since all primal flow changes decrease the kilter number of at least one of the links involved in the cycle by one, the new network is at most one cycle change away from optimality. That cycle change (if necessary) must involve increasing flow on Link k by one unit. This result implies that a cycle cannot include increasing flow along any other link which has the samle terminal node as Link k. Otherwise, the result would not be a cycle. Similarly, the cycle cannot include increasing flow along any link which has the same initial node as link k. These two observations w\ill )' neelded later in the proofs of convex marginal return functions for links having either a common iiltial or termilal inode. To deveflop the idea of convex mlarginal return functions, consider a minimum cost. network flow proletnM ill whicl Liink 1 flows from Node 1 to Node 3 and Link.2 flows from Node 2 to Node 3. For a particular realization of O, the upper capacity of iink 1 is u/13 = 913 and the upper capacity of Link 2 is I1-3 = 023- For simplification, assume that onlv thliese two links have stochastic capacities, so that prograiii (1) can be viewed as f(013, 023). Figture 1 gives a partial diagram of a possible network depiction of tills sit nation. Claim 3.1 f(013 + 1.023) - f(013,023) < f(O013 +- 10'23 + 1) - f(013,023+ 1). Proof: Let the all components of the optimal solutioll to f(013,023) have an accent bar (2'), all coni

Figure 1: Link 1 and Link 2 with a common terminal node. ponents of the optimal solution to f (013 + 1. 023) have an accent breve (i), all components of the optimal solution to f (013, 023 + 1) have an accent hat (~-), and all components of the optimal solution to f(013 ~ 1. 023 + 1) have an accent t Ilde (i). Suippose ij K< 01 This implies t hat 1 (013, 023) f f(O13 + 1, 623). Then, when 'U93 is raised t~o 023+1I ill 1(013 4-~ 1.0(23 + 1), by the comments above. i1, remains less than or equal to 613. This implies that, 1(0 1:3, 023 + 1) f13 + 1. Q23 + 1). Th-Iis shows t ta mt the claim is valid when <i ~13 or x9 K 023 (since tHie sante argument can be repeated). Assumne Ji = 1 + 1 and X- 2 + 1. SitIPPoS( t hat I ~< 013. This implies that f(Q13. 2 +1 1(013 +I-1.3 0231). Since f (0) isannicesng fttttct ion of 6, we know that. f (013~ 1 p,23) ~ f(0 13,23). Hence, tHie claim remains valid. Again, the samie argumient can be repeated for i-2* 9

Flinally, assume =i 613 + 1 2=623 + 1, xi 0 13 + 1, and x2) =023 + 1. Examine what, happens in each problem. 1. -f(O13, 623) =>Optimal flow X- has value f (613, 023). 0i13, Il - 113 > C13, otherwise i1 < 6~13. ~2 - 23,112 - /13 > C'23, otherwise i2 ~ 023. 2. f (0 13 + 1, 023) Optimal flow i has value f (O13 + 1 23). 11l -- 013 + 1, by assumption. PI - 13 Ti -/3 > C13, (,til t since Node 1 E X iandual variable change; otherwis a, circuit. would have been found). ~ 023 and Ji2 - /13 > C-23. Otherwise 12 K< 023. /13 > f1.sIc n dual varialble change strictly increases p for all nodes in X., and Node 3 is always in X1 (since link 1 is the only out-of-kilter link). Thten by Equpation (2). since thle only difference bet ween flow X- and.~ is the circuit, including( link 1 and] the only. possible links %which could be included in that circuit. othler thtan Link I accordling to the Out-of-Kil1ter method are thiose links (k, 1) for whichi 1k - /1I - Ckl 0, the followingf is established: f (O13 ~ 1, 023) = f013. 023) - (C13 - /11 + /13)013 + (C13 - fti ~,U3)(13 + 1) f f(O13o213)+(C 13 -P I + P3). (3) 1 0

Since the return to in-kilter was by circuit, C13 - M11 + J3 < 0. 3. f(O13. 023 + 1) = Optimal flow k has value f(013, 23 + 1). Xl =- 13, and /i - /3 > cl3. Otherwise i1 _< 13. x2 = 023 + 1, by assumption. 12 - -3 = P2 - 13 > C23 and P3 > 13. Again, by Equation (2), f(0 13, 623 + 1) = f(013, 023) - (c23 - P2 + /3)023 + (C23 -,2 + /3)((523 + 1) = f(013, 023) + (C23 - 12 + 13). (4) By assumption, the return to in-kilter status is by circuit. Hence, C0-3 - 12 + 13 < 0. 1. f(ol3 + 1. 03 + 1) (starting with feasible flow i1) = Optimal flow i has value f(o13 + 1. 23+ 1). 1 = o1: + 1., = 1. by asstulmption. /12 - /13 =- 2 - /13 > C23. /i1 - 113 > c13 and 13 > [3. By Equatiion (2), f(oi3 ( - 1. 03 + 1 ) = f(013 + 1. 23) - (r P - /' + P3)023 + (C23 - 2 + 3)(023 + 1) = f(o13 + 1. 023) t (c. - 42 + 13). (5) 11

Similarly, starting with feasible flow i, Equation (2) gives: f (013 + 1, (P23 + 1) f f(013, 0p23 + 1)-(C13 - fi + /'3)013 - (C13 - /11 '+ /13)(0~13 + 1 f f(013, 023 +1) + (C13-f1 + 3) (6) Now, from f (O1 23,consider the possibility of increasing both U13 and Ua23 by 1. Regardless of which link is chosen first, Node 3 must be labeled (+., 1). Thus, ifa circuit to either Node 1 or Node 2 is sought starting from labeled Node 3, one node must be reached before the other. and, until one is reached, neither p,i or 112 is icesd iandual variable change. Thus, either #2=/2 or fi=~ Without loss of generality, assume li, = jI1i. Then, using equations (3) and (6), f ( 1 3 + 1, 023) - f (0l3, 023) - f(O13 + 1, 023 + 1) + f (O13, 023 + 1 - /-3/'3 < 0. 'IlThs. the claim is valid. El Next, the Same property will be shiowii for liniks hain-ig a common initial node. Here, consider a nietwork flow problem in which Link 1 flows fromt Node I to Node 3 and Link 2 flows from Node 1 to Node:3. For a lparticular realization of o, t he uipper capacity" of Link 1 i 12=12ad the upper capac~ity of Link 2 i 3= 1 For simplification. a~ssuiie that onlyv these two links have stochastic capacities, so that program (1) can be viewed as f (013. 01-2). Figuire 2 gives a partial diagram of a possible network depict ion of this situation. 1 2

(112,12,C1l2 Figure 2: Link 1 and Link 2 with a common initial node. Claiim 3.2 f(oi2 + 1.013) - f(12, i013) < f(<12 + 1 013 + 1) - f(12 013 + 1). Proof: Th is proof closely matches that of Claim 3.1. Let the all components of the optimal solution to f(\l;\. c012) have an accent bar (i-). all componenits of the optimnal solution to f(013 + 1.012) have an acce't breve (1 ). all components of the optimal solution to f(013, 012 + 1) have an accent. hat (x), and all coImpoltents of-the optimal solution to f(613 + 1. 012 +- 1) have an accent tilde (x). Suppose 1-i < 013. This implies that f(013, 012) = f(oi3 + 1, 012). Then, when u12 is raised to 12} + 1 froim f (oli3 + 1. 012 + 1), by the comments above. w\e kniow% that i1 remains less than or equal to 013. Tr is i<mplies that (O13, 012 + 1) = f(13 + 1. 01'- 1). This shows that the claimi is valid whelen an < 013 or r', < o 12 (since the same argument can be repeate(l). Assumle '1 = 013 + 1 and x2 = (12 + 1. Sutppose that x1 < (13. This implies that f(13, P12 + 1) = 13

f(013 + 1, q12 + 1). But since f(q) is a non-increasing function of;, we know that f(is13 + 1,Q12) < f($13, 612). Thus, the claim remains valid. The same argument can be repeated for x2. Finally, assume x1 = 913 + 1, X2 = <12 + 1, X1 = 013 + 1, and x-2 = 12 + 1. Examine what happens in each problem. 1. f(i13. 12): Optimal flow x has value f(013, 12). 1 = (13, /1 - -3 > C13. Otherwise, l < 013. '-_, = 012, - 12 > c12. Otherwise, 12 ~< 12 -2. f(013 + 1, 12) = Optimal flow x has value f(13 + 1,4 12). 1 =- 013 + 1. by assumption. l1 - P3 = /1 -3 > C13. (1i = Pi since Node 1 E.V in any dual variable change; otherwise a circuit would llave been found). 1-, =- o1' and /1 - 12 > C12. Otherwise, i2 < 012. /13 > /13. sinCe any dual variable clhange strictly increases p for all nodes E,'. and Node;3 is always in.' (since Link 1 is the only out-of-kdltcr link). Thell by) Equation (2). since the only -differeiic t)etween the flow x and i is the circuit ilcludlilng Link 1 and the only possible links whiclh cotuld be included in that circuit other than Link 1 according to the Out-of-Nilier mlet lod are thlose links (k, 1) for which k - i - ckl = () tie following is established: f(013 + 1.012) = f(O13. 012)- ('1:3 - -l1 +.3)O13 + (C13 - /1 + -13)(913 + 1) = f(o13, 012) + (13 - /i1 + /3). (7) 14

Since the return to in-kilter was by circuit, C13 - 1 + [3 < 0. 3. f(13, 12 + 1) = Optimal flow x has value f(013, 012 1). Xl = P13, and i - /3 > C13. Otherwise, x1 < 013. '2- = 12 + 1, by assumption. 11 -P12 = P1 - -2 > C12, and /i1 > P1. Again, by Equation (2), f(013. 012 + 1) = f((P13. 12) - (C12 - -1 + "2)l12 + (C12 - F1 + P'2)(12 + 1) = f(13, 012) + (C12 - f1 + P2)- (8) Since, by assumption, the return to in-kilter status is by circuit, C12 - I1 + /12 < 0. -1. f(o:t + 1. o12 + 1) (starting with feasible flow x) > Optimal flow x has value f(ol3 + 1,01 -+ 1). J'l = 013 + 1.x'2 = 012 + 1, by assumption. /1I - 112 = P1 - 12 > C12 -/ll - 3 > c13 and,3 > P3. By Equation (2), f(013 + 1.012 + 1) = f( 13 + 1 012) - (CL' - l1 + 2)12 + (c12 - 1 + P2)(12 1+ 1) = f(013 + 1,012) + (C1' - 1 + I2). (9) 15

Similarly, starting with feasible flow i, Equation (2) gives: f (p13 +1, 02 +1) f(1i02+1 C3-il+~)1 C3~ i)63+1 f f(13, 012 + 1) + (Cl3 - pl + /13). (10) Now, from f (~13, 012), consider the possibility of increasing both U13 and U12 by 1. Regardless of which link is chosen, a cycle is not found resolving either out-of-kilter status until Node 1 becomes labeled. Thus, until Node 1 is reached, /11 is not increased in any dual variable change. Thus, either P2 = 112 or =I-LI Without loss of generality, assumne p, _-ti* Hence., uising equations (7) and (10), f (O'13 + 1, 012) - f (O13, 412) - f(10 1 + 1, 0~12 + 1) + f (~1 3, 012 + 1 - 13 -113 < 0. ~1li..the claini is valid. 13 4 Upper Bound for a Non-increasing Convex Function with Convex Marginal Ret urn Functions Let P1 be aniin-dimienisional random %sector. w Ierc (dch 4)1 is independently distributed with a. bouinded suppo~t' finite mean anid cumulative dist ribut ion fiiict ion F7. Further, let, H~ be the realizations of 16

(Di defined as: (L = 1iF(6)<0,(1 1) so that. Lf < O[H for all i. Let pL =prob{f 2D = qL I and pH1 prob{f~ =I~ O'} for all i be such that Let, f (4)) be a non-increasing convex function of (D with convex marginal return functions with respect, t~o any p air i((2 I) i_ 1,., n, j=1.. n. Then the following proposition, proven in Donohue and Birge [8]. shows that an upper hound on E[f ((D] can be established with only 2 function evaluations. Proposition 4.1 Let (D and f((D) be as defined abov~e. Lei pL = maxlp~pl P1... I and 1 Th(ii E[f (()] < 1L(Q 2 L ~"f<.' IHa\itig shown that the iminimumi cost net-work flow problem with stochastic upper link capacities is a ioni-Hicrea.siiig, conv\ex function of the stochastic tipper capacities, and that this function also has conv~ex inarginial ret urn functions wit~h respect to capacities of links having either a common initial or commnon ternmimal node. Proposition 1 can be applied to solve for ati uipper bounld on the expect~ed value of this stoclhast c mnin'n D cotntork prograni which inovssolving 2k1 or 2k2 realizations, where k1 is thle inuiuiber of nodes having outbound links withi stocia-St ic tipper capacities and k2) is the numiber of nodes Ihavimng inlbound links with stochastic upper capacities. In mnany cases, this is a significant reduction to the 2L realizations that are needed to be solvedl for thme Edmundson-Madansky bound, where L is the inumber of links heaving stochastic upper capacities., 1 7

Consider a network in which link i has stochastic upper capacity Oi, i = 1,.... k. Then by the Edmunson-Madanskv [1 1] bound, k i1E{fL, H} i kE{LH} j=l Let ni, nh be the set of terminal nodes of links 1,.. k. Let ti denote the terminal node of link i, 1..k, and let. pL maxjpf L = j},p' = 1 -p. Since f((D) is a non-increasing, convex functoion with convex marginal return functions, Proposition 4.1 can be applied over each set of links with a common term-inal node. Hence, h E[f (1))] < (pj)f.q,['.<) (14) j.iE{LH} j hE{fLH}l= Similarly, by letting I, denote the initial node of link i, the same inequality results from applying Propositoion 4.1 over each set. of links with a common initial node. Refinements of t~he bound in Proposition 4.1 are foun-d inl [8] which can be applied here to improve the effectiveness of this bound. 5 Experimental Result T'o test the effectiveness of this upper bound, two test problems were creat~ed and solved. Thel( first I)rolblemn is a transportation problem with 15 source iiodes. 15- sink nodes and 105 links connecting the sources anid slinks. Three different. versoions of this problemn were considered. The seconid lproblem is a Ve1hicle allocation problem with uncertain (Ie-inaIIlS. This typ~e of problem determines the expect~ed value of' a specific initial vehicle distribution, given1 nlicert aiuit about. the demand for vehicle routings alonlg several or all liniks. This problem has '20 niodes anid 92) links,,. Th-lre-e versoions of the transportation probleuin were considered. First, all 105 links were assumed t~o be stochastic. making finding an upper bounid using Edmunidsoni-Madansky computationally impossible. 1 8

Dist. Number,i Li Hi Pr(Xi = i) Pr(XX = L 1) Pr( L + 2) Pr(Xi = Li + 3) 1 1 4 0.35 0.30 0.25 0.10 2 2 5 0.40 0.20 0.20 0.20 3 3 6 0.30 0.25 0.25 0.20 4 4 6 0.50 0.30 0.20 5 5 8 0.40 0.30 0.15 0.15 6 6 8 0.45 0.35 0.20 7 7 9 0.50 0.25 0.25 8 8 11 0.35 0.30 0.20 0.15 9 9 11 0.45 0.40 0.15 10 10 12 0.40 0.35 0.25 Table 1: Possible Distributions for Links with Stochastic Upper Capacity for Transportation Problem. Next. 3() of thle links were randonmly selected to have stochastic upper capacities, and each of the other linksl were given capacity near the mean of its respective distribution. These 30 links had 9 common t-ermiiinal nodes, allowing an upper bound to be found with 2= 512 function evaluations. Finally, all of tlli links otut of node 8 were considered stochastic, giving a total of 9 stochastic links. Here, an upper houllnd is established with just two function evalulatiois. Further, a refinement of the upper bound by partitioiling was calculated for comparison. Table 2 lists the cost per unit flow between all sources and siks, wllere flow between the corresponding notdes is possible. Table 3 lists the supply and demand reqllirellent.s at. each of the source and sink nodes. I aclh link has a lower capacity bound of zero. The distriblltion of thle random variable corresponding to the upper capacity of each link was one of ten 19

ti t2 t3 t4 t5 t6 t7 t8 t9 tio tll t12 t13 t14 t15 sl 109 323 - 96 107 230 380 254 352 -- - 385 s2 - 105 - 99 - 405 - - - - 428 249 158 s3 - - - 315 - - 217 66 - 139 73 '157 - - - S4 202 - 175 277 - - 402 290 - -- 233 - - - sc - 123 - - - - - - 167 94 169 296 154 447 - s6 - - - 143 - - 216 382 - 112 229 149 - - - s 291 - 127 - - - 279 - 226 436 sR - - 388 137 280 239 - - 81 318 201 245 - 97 59 384- - - 334 339 - 137 317 - - - 65 sio 197 - - - 357 - 415 362 272 246 223 - 393 -. i - 442 - 257 242 307 420 - 119 - 384 - 149 - 209.s, i 17 - 136 - - 186 - 111 - 322 - 106 - - 312 sl 1 59 267 - - 67 76 - 362 427 401 - - 174 - -.14 - - 244 - 110 291 -' 11 - -29 228 - 05 3s, i.- -- 426 35()0 97 94 355 Talite 2: Cost per unit flow from source.s, to sink tj in Transportation Problem. z= 1 2 3 4 5 6 10 11 11 2 13 14 15 s, 55 46 35 26 44 38 421 58:3 44 32 46 50 34 30 f, 47 32 23 43 13 59 5(.011 44 72 38 47 30 30 31 Table 3: Source and sink node supply andl (demalld requirements in Transportation Problem. 20

possibilities. Let Xi denote the random variable with distribution i, and let Li (Hi) denote the lowest (highest) possible value of distribution i. The ten possible distributions are listed in Tab'l 1. Table 4 gives the distribution that was assigned to each link. The second problem is a vehicle allocation problem, one stage of a dynamic vehicle allocation problem with uncertain demands (see [13]). Figure 5.1 depicts the network over which the fleet of vehicles must be routed, given the initial distribution of vehicles at the source nodes 1 through 5. The problem only requires that flow is conserved throughout the network, given the initial distribution of vehicles. Thus, Node 20 is actually an artificial sink node and the links into Node 20 are artificial as well. These links are uncapacitated and add no value to the problem. All other links shown in the diagram handle the flow of loaded vehicles between the adjacent, nodes. Since the need to move loads is governed by demand, the upper capacities of these links are stochastic. Flow along these links generate positive revenue. Running parallel to each of these links, but not in the diagral. is another link which handles the flow of enlpty vehicles. These links are uncapacitated. Flow along these links generate positive cost. The goal is to mintimize negative profits (cost - revenue). The givenl initial distribution of vehicles is (10,12.12,10.7). The links in this problem were numbered by collsid(lrinlg each node in numerical order (as seen in the diagram) and numbering consecutively from top to bottom. Table 6 gives the cost per unit of loaded flow along each link (ri), the cost of per unit. of ellpty flows along each link (ci), and the distribtioll givell to the random variable corresponding to that link's upper capacity(Di). As before, the distriu)itionls were chosen from among 10 different possibilities, wliicll are shown in Table 5. Againll three versions of this problem were colsidered. In the first version, all of the links handling the flow of loaded vehicles were assumed to have stochastic upper capacities. In the second version, 15 links 21

l t2 t3 t4 t5 t6 t7 t8 t9 tlo tll t12 t13 t14 t15 s 8 5 - 9 1 9 5 - 9 10 - - - - 3 s2 - 10 - 7 - 1- - - 1 10 10 s3 - - - 2 - - 7 8 - 5 6 9 - - - 4 8 - 3 6 - - 3 8 - - - 1 s5 - - - - - - 7 6 9 7 8 6 - - 9 - - 4 3 - 6 10 8 - - - s; 6 - 6 - - - 6 - 2 s - - 7 6 2 8 - - - 10 7 8 10 - 3 s 1 - - - - 4 8 - 7 10 - - - 9 - slo 10 - -2 - 1 1 0 9 7 8 - 1 1 - 9 1 4 9 - 3 - 2 - 2 - 4 6 1 - - 9 - 7 - 8 7 - - 10 s,. 10 9 - ( 2 9 - - - S14 - - 7 - 8 7 - - 2 - 8 - ~s. 2 - 7 - - 8 6 3 Table 4: Distribution for upper capacity of link from source.s to sink tj in Transportatioin Problem. 22

D, L, Hi Pr(X1 = Li) Pr(Xt- = Li + 1) Pr(X1 = L1 2 Pr(X1 L1 + 3) Pr(X, L2 + 4) 1 0 2 0.40 0.30 0.30 — 2 0 3 0.40 0.2-5 0.2-0 0.15 3 0 3 0.35 0.25 0.20 0.20 -4 0 4 0.30 0.25 0.20 0.15 0.10 5 0 4 0.35 0.20 0.15 0.15 0.15 6 1 3 0.45 0.35 0.2-0 - - 1 3 0.40 0.35 0. 215 - - 8 1 4 0.45 0.20 0.20 0.15 - 9 1 4 0.40 0.25 0.20 0.15 - 10 2 4 0.40 0.30 0.30 - - Table 5: Possible Distributions for Stochastic Links in Vehicle Allocation Problem. wer coseni at random to have stochastic capacities. These 15 links have 8 distinct initial nodes and 11 (listiimet terminial niodes, so that the upper bound from links with a com-mon terminal node differs only slgtyfromt the Ed Imundson-Madaniskv bound. both in value and computation. The upper bound fromt linksd withi common initial nodes. though. is small enioughi that that probability space can be partitioned anr(l the initial tupper hound can be refinied. Finially, all flinks into and out. of Node 8 are assumed t~o have stochlastic t'prcpctes. Thus. a total of eighit liniks hav~,e stochastic caactes. Since the nietwork i acv~clic. iioiiel of the links into Node 8 are affectedI wlwii tw li lound for links withi a common initial node I IiSe(I( over t he l'inks out. of Node 8. hlence. t li bound for l'inks with a common terminal niode can be liseI(l on aill tHie links into Node 8. Thus, onfly four furict ion evaluations are necessary. A prog-ram was written in C which recursivelv updated the right-hand side of each network problem 23

i ri ci Di i ri ci Di i ri ci Di i ri ci Di 1 327 81 4 13 255 73 1 25 177 63 9 36 263 93 4 2 211 67 10 14 265 76 3 26 348 91 10 37 285 98 7 3 243 70 1 15 360 105 9 27 148 51 10 38 281 99 7 4 268 70 7 16 161 60 10 28 312 76 8 39 242 87 1 5 204 73 3 17 264 78 8 29 332 83 9 40 301 108 6 6 301 75 10 18 348 86 10 30 284 75 3 41 277 93 4 7 356 95 8 19 267 78 8 31 317 76 6 42 168 77 5 S 190 63 5 20 146 54 7 32 367 103 6 43 175 78 7 9 225 69 1 21 330 86 4 33 329 81 2 44 273 94 8 10 198 66 1 22 352 93 2 34 214 65 9 45 252 87 3 11 343 85 2 23 188 61 6 35 326 78 1 46 252 88 2 12 261 80 3 24 225 7:3 lable 6: Revenue for loaded flow, cost of emll)t flo. anl distribution of capacity for links in Vehicle Allocation Problem. 24

Figure 3: Vehilcle Allocation lProbleml with Uncertain Demands 25

as needed, then passed the new program to be solved by IBM's Optimization Subroutine Library (OSL). The program was run on an IBM RS\6000 workstation. The results are shown in the table below. The table includes information about the number of stochastic links in each version, and the number of distinct problems that had to be solved. If two values are shown for the number of problems solved, the first is for the upper bound for links with a common terminal node. the second for links with a common initial node. If only one value is shown, the values are the same. Also shown is the optimal objective value when all stochastic components are at their lowest value (Greatest Objective Value), and the optimal objective value when all stochastic components are at, their highest value (Least Objective Value). This was done to show the range of possible values. Finally. the table shows the lower bound found using Jensen's Inequality, the upper bound using links with a common terminal node, and the upper bound using links with a common initial node. The problem TIranls.:3.a shosws the effect, of the refining the bound in problem Trans.3. Problem Veh.Allo.3 shows the h)oiii(d oh il'ied by clusterinlg both tlie links into Node 8 and links out of Node 8. 26

Number of Number of Greatest Least Lower Upper Upper Problem Stochastic Problems Objective Objective Bound Bound Bound Links Solved Value Value (Jensen) (Terminal Node) (Initial Node) Trans.l. 105 15 132,095 114,190 124,154.90 126,838.00 126,671.59 Trans.2. 30 29 132,095 126,007 129,519.45 130,064.32 130,098.17 Trans.3. 9 2 130,303 127,165 128,766.40 - 129,126.25 Trans.3.a 9 3 130,303 127,165 128,766.40 - 129,054.28 eh. Allo. 1 46 214 -2058 -33270 -17,835.50 -16,082.53 -14,831.20 Veh.Allo.2 15 21128 -8038 -20.258 -13,179.10 -12,912.32 -12,558.45 \;eh.Allo.3 8 4 -6861 -16952 -11086.65 -10787.42 Thlle hounds for the Transportation problem are remarkably tight. as the upper bound is within 2VS of thie loNwer bound in all cases. and as close as.2247 in problem Trans.3.a. This would suggest that the funllction is almost linear in the stochastic capacities O, and that Jensen's inequality is very close to the actual expected value. It is reasonable to assume thlat more error exists from the upper bound here than the, lower bound, as is typically the case with colvex function approximations. Note, however, that the effectiveliess of Jensen's inequality in this probleml woouldl be more difficult to prove without an effective til)per boulld. The best upper bounds for problcm.l \'Ve.Allo.1, Veh.Allo.2, and Veh.Allo.3 are within 9.8(. 2.0(,. and 2.7t%(, respectively. of the givenl lo\(wr bound. 27

6 Conclusion As stochastic programming reaches new heights in the number of realizations of the second-stage problem parameters being considered, new methods must be developed for approximating the expected value of recourse functions of even more realizations. To know the value of any approximation method, tight bounds, both upper and lower, must be available on the expected value of the recourse function. Finding effective approximation methods for stochastic programs often requires that problem structures be exploited so as to maximize computational efficiency. In this paper, we exploited the structure of minimum cost network flow problems in such a way as to allow an effective upper bound to be established v.ith a reduced number of function evaluations. Furtlher. the ideas of this paper may possibly be extended for special cases where the flow through certain nodes can be shown to be independent of one another. Also, the results of this paper also suggest ideas for better partitioning methods used for refining lower bounds. Given the result about coinvex irgtinal return functions, it seems likely tlhat e best partitioning order is going to be one whicl I)artitionll on links having as few common initial and terminal nodes as possible. 28

References [1] Mi. S. Bazaar, J. J. Jarvis and H. D. Sherali. Linear Programming and Network Flows. John Wiley k Sons, New York (1990). [2] J. R. Birge. Decomposition and Partitioning Methods for Mulitstage Stochastic Linear Programs. Operations Research 27 (1985) 989-1007. [3] J. R. Birge, C. J. Donohue, D. F. Holmes, and 0. G. Svintsiski. A Parallel Implementation of the Nested Decomposition Algorithm for Multistage Stochastic Linear Programs. Mathematical Programming, to appear. [4] J. R. Birge and F. Louveaux. Stochastic Programming. unpublished manuscript, 1995. [5] J. R. Birge and R. J-B. Wets. Designing Approximation Schemes for Stochastic Optimization Problems, in Particular Stochastic Programs with Recourse. iMathematical Programming 27 (1986) 54-102. [G] H. NI. ('heungand \N'. B. Powell. An Algorithm for IMultistage Dynamic Networks with Random Arc ('aIMpacities. with anl Application to Dynamic Fleet MIanagement. Operations Research, to appear. [7] (. Iallatzig. Linear Programming iunder liicertallnty..Mlanagement Science 1 (1955) 197-206. [S] ('...1. )onohue and J. R. Birge. An Ilpper Bou(nd on th Expected Value of a Non-increasing Convex Funllction with Convex Marginal Return Fuinlctiolns. \Working Paper, Department of Industrial and ()perations Engineering, University of Nlicliali. \IAn Arhor, Michigan (1995). [9] I. F.. Frantzeskakis and 1N'. B. Powell. Boidiing Procedures for Multistage Stochastic Dynamic.N et\works. Networks 23 (1993) 575-595. 29

[10] D. R. Fulkerson. An Out-of-Kilter Method for Minimal-Cost Flow Problems. Journal of the Society of Industrial and Applied Mathematics 9 (1961) 18-27. [11] A. Madansky. Bounds on the Expectation of a Multivariate Random Variable. Annals of Mathematical Statistics 30 (1959) 743-746. [12] K. G. Murty. Network Programming. Prentice Hall. New Jersey (1992). [13] W\. B. Powell. A Comparative Review of Alternative Algorithms for the Dynamic Vehicle Allocation Problem. In B. I. Golden and A. A. Assad. (eds.), Vehicle Routing: Methods and Studies. NorthHolland (1988), 249-291. [14] R. Van Slyke and R. J-B. Wets. L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Linear Programs. SIAMi Journal of Applied Mathematics 17 (1969) 638-663. [15] D. \\'alkup and R. J-B. W\ets. Stochastic Programs with Recourse. SIAM Journal of Applied Mlathcmatlics 15 (1967) 1299-1314. [1(] S. \V. \allace. Solving Stochastic Prograims with Network Recourse. Networks 16 (1986) 295-317. [17] S. \\. \allace. A Piecewise.Linear lUpper Bound on the-Network Recourse Function. Mlathematical Programnmining 38 (1987) 133-146. 30