The Relationship Between the L-Shaped Method and Dual Basis Factorization for Stochastic Linear Programming John R. Birge Technical Report 82-15 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 September, 1982

The Relationship Between the L-Shaped Method and Dual Basis Factorization for Stochastic Linear Programming John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109, USA Abstract The basis factorization method of Strazicky for stochastic linear programs is shown to involve the same computational effort per iteration as the L-shaped method of Van Slyke and Wets. A variant of the factorization approach can then be found which is equivalent to the L-shaped method. The advantages of this decomposition approach over a standard factorization are discussed.

The Relationship Between the L-Shaped Method and Dual Basis Factorization for Stochastic Linear Programming 1. Introduction We consider the problem min cx + Q(x) (1) subject to Ax x > 0, where Q(x) = E;[min q y subject to Wy = C - Tx, y > 0]. and 5 is a random n2 - vector, where m2 x n2 real matrix, T is an m2 x n correspondingly dimensioned vectors. F1;2 i N For C E 3 = to,,..., 1, where equivalent to A is an m1 x real matrix, nl real matrix, W is an and c, q, and b are P(S = i) = p, we have (1) is min 1 1 2 2 N N cx + p q y + p q y +... +p q y subject to Ax Tx + Wy - b = 1 Tx + Wy -e2 (2). Tx + N + Wy -N 1 2 N x, y, y,..., y > 0.

2 The dual of (2) is T 1 1 1 22 2 NN NN b a+p TrT + p IT +.. +p T max subject to T T AT 1 1 2 2 NTN A p + p T.I +. + p T T T c wT 1 W 7T T wT 2 W ir (3) T, q q T < q WT rN W tr Kall [1979] and Strazicky [1974] observed that any feasible basis of (3) may be written as (4) B * Y where B is a block diagnal matr where B is a block diagonal matrix. For (3), r 1 4m I I - I IT L2 I0 I I 1gf - OMMMMWA -11 iN I IN I I I

3 where [WT I ] is an n2 x n submatrix of [WT I] for all i ~I2 2 i = 1, 2,...,N. Kall notes that we may reduce the size of [Wi I] by taking an m2 x m2 nonsingular submatrix W. from W We have 1 i (5) KI K ^ A +_P -TlA AT -T A-i - AT -1 A I *?i(6) +^ (6) substantially reduces the number of rows from (5) but it has a significant draw back in terms of nonzero element storage. The sparse matrix TT T A (AT -T AT-l may be transformed into a very dense matrix (W. )(W). (6) A more practical approach would be to store the inverse of Wa. for the current basis (where Pi = 0) and to generate elements of (W.)(Wi) as needed. LU decomposition and sparse updating may be used to improve this approach. It may also be shown that this method involves the same computational effort per iteration as the L-shaped method of Van Slyke and Wets [1969] and that a modification of the dual basis factorization method will follow the same path as the L-shaped method. This modification amounts to the dual decomposition procedure proposed by Dantzig and Madansky [1961].

4 2. Discussion We assume we have a feasible solution to (3), (a, T7r,7T, 2 I, 0 1,0 2,0 N,0 0 1,0 2,0 NO X,, p,...., p0 ), where X, p,p,.,p ) are slack variables. We also assume that W. = W for all i so that only columns from A and the identity are basic in the first set of constraints. In the pricing operation, we solve AxB + A xN b, INXN = 0, where I is the set of basic identity columns. We have xB = (A )b and N B check for xB > 0. If some x (i) < 0, then that column in A is replaced and the problem is solved again. If we restrict ourselves to only checking for primal feasibility in the x variables, thenwe are solving the dual problem T max b a T T i T i,0 subject to A T < c - Z pT i=l or the primal problem mn (c - Z p 'ri T) x min (c - Z p f ) x i=l subject to Ax = b (7) x > 0. This is essentially the first step of the L-shaped method. The dual method involves the same steps of computing A xB = b, TrA = c and N p = cN - irA as in the primal method, so the computational effort is the same at each step. We note that this does not include pricing for y variables as would occur in the general dual method.

5 After all x (i) > 0 have been found, we let x be the prices and B - i i 1 i we proceed to solve W y = - T x for all y. For every subproblem i, if yi(j) < 0 then we choose a leaving column only from the identity columns in subproblem i. We relax dual feasibility in the first set of constraints. This process is equivalent to solving the subproblems i min q y i i 1 (8) subject to Wy = - T x, y > 0, for all i as in the L-shaped method. We note again that the computations involved in a single iteration are the same in both methods except that we do not update the prices in the first set of constraints for the factorization method. We note also that solutions of (8) may be found quickly by finding all i for which a given basis is optimal. After solving these problems, we obtain either an unbounded condition or all y > 0 * In the former case, some subproblem (8) is infeasible. We then look at the column in (3) which gave the unboundedness i i 7k-1 condition. For y < 0, y. = (i) (j,-) (j-Txl) and the column - [(i) (j).Wi]T < 0. We let T = -(Wi)(j-) and obtain (9) T (i - Tx1) > 0, and (10) rT W. < 0. 1 = (9) and (10) are the infeasibility conditions for (8) that we would find in the L-shaped method. In the dual method, we would choose a pivot from the first set of constraints so that we would force ir (i - Tx) < 0.

6 We introduce a new column in the main problem, pi( 7iT P i i T (Pi TT7T)p where p > 0. The main problem is then T i i iT max b o + p (~ T +r)p T i T i -T subject to A + (pT r)p < c, P > 0, -T T where c includes c and other fixed columns of IT. This is equivalent to adding a constraint (iT T) x < 1i, as in the L-shaped algorithm. We next solve the main problem again and repeat. If after solving the subproblems all y i 0, then either the problem is optimal or one of the first set of constraints in (3) has been violated. N i iT T i1 In this case, if we let e = Z p (( ) - (Tx)1 r, where iT is i=l the initial solution of (3), then we have N i T T i 2 0 < Z pi((i) - (Txl) T)T' i=l i,2 where r is the optimal subproblem i solution. We observe that either i,1 i,2 T 9 or f ir or linear combinations of these solutions may be used to for solutions for the subproblems. We use this to obtain a substitute first period problem:

7 max T N i T i 1 N )i T i 2 b + ( Z pi ( ) T' ) + X i( Z p i ) Tr ) 1=1 i=1 subject to N N T-, ^ / N ^riT i,2 N AT0 + X1 ( p ) iT ) + 2( Z ( i)T ' ) < c i=1 i=l (11) 1 + = 1 X1, X2 > 0. We solve problem (11) and repeat by adding a column for feasibility of the subproblems or by adding a column for choices of subproblem solutions as in (11). We note that these are the same steps as in the L-shaped decomN i iT position method where 6 < E p ((S ) - (T x1) ))TT and a constraint on i=l (12) N N iT ( Z -iT) x + 0 > Z P (i ), i=l i=1 is added. The two methods with procedures for each iteration. the same steps as Dantzig-Wolfe (3), (Dantzig-Mandansky [1961], these specifications follow the same We note also that these methods follow decompostion applied to the dual problem Van Slyke and Wets [1969]).

8 3. Conclusion We have shown that on each iteration of the L-shaped method, the number of steps is equivalent to that of the basis factorization method and that the L-shaped method may be viewed as a variant of the basis factorization approach. In general, however, the two methods will not follow the same path to optimality. By maintaining dual feasibility, the basis factorization restricts the path to optimality and requires more effort in checking for feasibility within the first set of constraints. The decomposition variant of basis factorization also avoids two other problems inherent in the full factorization approach. For X = B- Y in (4), the factorization approach uses the inverse of (L X - Z) in performing simplex operations. X is composed of columns of B1 since Y is composed of identity columns. The columns of B need not be sparse and may be very dense, causing (LX - Z) to be dense as well. The storage requirement for the nonzero elements of this nl x nl matrix may be large. Another difficulty in applying this factorization without decomposition is that, whenever an identity column in I. in (5) is replaced, ~~m~~~~~1 then fT must be changed and (LX - Z) changes. This pivot alters the prices x for all other blocks j + i. Therefore, a pivot step is required for each new block into which this identity column enters. By ^T fixing x in the decomposition, whenever a new matrix W. is introduced, all values such Tx) > can be found without all values ^ such that y^- (Wi) (~ - Tx) > 0 can be found without performing separate pivot operations. For very large N, the standard factorization scheme may be forced through a long sequence of pivots,

9 whereas the decomposition approach may change these bases quickly. For problems with large N, then, the decomposition variant above is probably the only tractable basis factorization method. Ref erences G. B. Dantzig and A. Madansky, "On the solution of two-stage linear programs under uncertainty", in Proceedings, 4th Berkely Symposium on Math. Stat. and Prob., University of California Press, Berkeley, (1961) 165-176. P. Kall, "Computational methods for solving two-stage stochastic linear programming problems", Journal of Appl. Math. and Physics, 30, (1979) 261-271. B. Strazicky, "Some results concerning an algorithm for the discrete recourse problem", in Stochastic Programming, M.A.H. Dempster (ed.), Academic Press, New York, (1980) 263-271. R. Van Slyke and R. Wets, "L-shaped linear programs with applications to optimal control and stochastic linear programs", SIAM Journal on App. Math. 17, (1969) 638-663.

UNIVERSITY OF MICHIGAN 3 9015 03994 8271