A Dantzig-Wolfe Decomposition Variant Equivalent to Basis Factorization John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Technical Report 84-3

1 Abstract A variant of Dantzig-Wolfe decomposition and basis factorization are compared as solution techniques for block angular systems. It is shown that the two methods follow the same solution path to the optimum. The result has implications for the use of decomposition and factorization algorithms together.

2 I. Introduction Many methods have been proposed for solving linear programming problems with a special structure. Block angular structure, in which subsets of the variables are only associated with certain subsets of the constraints, is a common example. Two basic approaches for problems with block angular structure are basis factorization (e.g., Dantzig [4], Winkler [8]) and Dantzig-Wolfe decomposition, (Dantzig and Wolfe [5]). Basic factorization, in general, is a procedure for simplifying the process of finding entering and leaving variables in the simplex method. Various types of factorization have been shown equivalent by Winkler [8]. Dantzig-Wolfe decomposition, or inner linearization (Geoffrion [6]), however, simplifies the problem differently by representing the solutions of separate blocks in terms of extreme points and rays. In this paper, we present a variant of standard Dantzig-Wolfe decomposition, and show that it leads to the same sequence of basic feasible solutions as followed by the simplex method using a pricing scheme consistent with basis factorization methods. This result generalizes the observation of Kallio [7] on a specific condition for identical pivot steps to occur in the two methods. It also extends the result in Birge [1] that Benders' decomposition and basis factorization of the dual of a stochastic linear program with recourse require the same computational effort per iteration. In the next section, we describe the implementation of the methods

3 on block angular systems. We then show how the Dantzig-Wolfe decomposition variant follows the simplex method steps. II. Problem Definition Many special structures in linear programming problems can be exploited by variations of the simplex method. We will use the following representation of systems with one such structure, block angularity. k i i Min. z = cx + E d y (1.0) i=l k i s.t. Ax + Z T y =b (1.1) i=l ii i W- y = h,..., k, (1.2) x > 0, y > 0i, =..., k, n n. m m. where x R, y e R, b E R, hi R 1, and vectors, c and d; and matrices, A,Ti and W are dimensioned accordingly. B Bi.. B., A basis for (1) is composed of columns A from A and [T 1W ] from [T.W ]. The basis is square block diagonal if A contains B.. B exactly m0 columns (and, hence, each [T:W ] contains m. columns). This property is especially useful since basic solution values B B (x, y ) can be found by solving B E1 B. a. W y = h, for i = 1,..., k, and then solving AB B = k B i B A x =b- ZT y i=l

4 When the basis is not square block diagonal, there exist additional Bi~ B] B subproblem columns [T W ] that replace columns in A. The basis then has the form B B BB B TB T... TBk TB1... Bk AT T T T B WB1 W W. D * B B k k W W [ABT 1 k i where [A T T ] is an m0 x m0 submatrix, and W is known as the secondary block i subbasis. The basis factorization in this method is to observe that B. B. B. B. i i)-1 i i i) (2) y (W (h -W ) (y (2) and B k B B k B. B B B A" x3 + 37 T\ y + E T (W )(h - W ) = b. -=l i=l Next, let B. B. B. B. B. T (W ) W and B. B. B. =T i(W ) This yields k.i B. B. B B -1 1 -1 hi1 A x + Z T y = b - T. (3) i=l The working basis is then [AB:T.. T ],

5 and the system can be solved by (3) and (2). Other forward and backward transformations can be performed in a similar manner. This basis factorization can be implemented with a variety of strategies. We choose a strategy that emphasizes dual feasibility 1 relative to the x and y variables, which we call the first block. Basis Factorization -First Block Strategy (FBS) 1. Start the Simplex Method (Phase 1 and Phase 2) with a square block diagonal matrix. (This may, for example, be an identity matrix corresponding to artificial variables.) B. 2. Whenever a block i subbasis changes or whenever a new y B. variable enters the working basis, fix the y variables, and B. choose the entering variable only from x and y, i = 1,..., k, if any of these variables is eligible to enter the basis. This amounts to solving (3) and using (2) to check for other leaving variable possibilites. If none of the x and y variables is eligible to enter the basis then choose the entering variable from y. If none of these is eligible, then continue to increase i until some yj is eligible to enter the basis. The extreme point path followed by the simplex algorithm under this startegy is also followed by a suitable variant of the Dantzig-Wolfe decomposition algorithm. The algorithm is based on the resulution of y into extreme points, y, and extreme rays, z i, of the region Yi i yi i h. y i = {y Wy = h, y > 0}.

6 If Y contains L extreme points and P extreme rays, (1) can be rewritten as the full master program k L i, P min z = cx + E { L (d iy )Xi + p i P i=l Z=1 p=l pi k L i i k i k ipi'p = b s.t. Ax + Z { (Ty' ) + X (T, b) i=l g=1 p=l L i, =1i i = 1,..., k, x, X i, ip > 0, all i, Z, p. Since (4) can contain an enormous number of columns, only a subset of the extreme points and rays are generally considered at a time. If Q. extreme points and pi extreme rays are coni sidered, then (4) is reformulated with Q and p replacing i i L- and P. This simplified problem is known as the restricted master program. Additional columns can be added to the restricted master program by first finding the optimal dual * * * 1 k variable values, (, ). An extreme point column i,g corresponding to y is eligible to enter, if dii, * iy i < (5) dV y - T y' - 8 <0, and an extreme ray column, z may enter if d izip - _ T'< 0. (6) (5) and (6) are generally checked by solving the subprogram m in. w = (di " Ti)yi (7) ii i s.t. Wy hi Y 0.

7 * * If the optimal objective value of (7) w > e for all i, then no column is eligible to enter the basis of the restricted master program. The optimal solution found for the restricted master is, hence, an optimal solution of the full master. If any basic feasible solution of (7) is found with an objective i value below 0 for some i, then that solution may be used to construct an entering column in the restricted master. If an unbounded solution of (7) is found, then an extreme ray column may be added to the restricted master. The restricted master is then again solved and (7) is again checked for eligible columns. The process repeats until no column is eligible to enter the restricted master basis. In the variant of Dantzig-Wolfe decomposition given below, the observation that (7) does not need to be solved to optimality to find an entering column is used to establish the equivalence of the algortihms under the given strategies. The variant also allows i, g certain X values to become negative as long as the solution y so obtained is still feasible. Dantzig-Wolfe Decomposition - Key Column Strategy (KCS) 1. Choose a basic feasible solution from each subprogram (7) to include in the initial restricted master. Designate the columns obtained from these solutions as key columns. Solve the restricted master (with, perhaps, a Phase I objective).

8 2. Let the basic feasible solutions that generated the key columns be the initial solutions for the subprograms (7). If no variable is eligible to enter the basis for any i, then, stop. If yj is eligible to enter the basis then add j to the set of supplemental variables at i, S. Pivot to the adjacent basis and add the column generated by that extreme point to the restricted master, or, if no pivot is possible, add the column generated by the extreme ray found in this procedure to the restricted master problem. 3. Re-solve the restricted master problem where the key column variables are always basic and are allowed to take on negative values. Solve until all reduced costs are nonnegative, or some pivot step leads to a solution which violates the set of inequalities zi i ii, -1 i (8) E (W < ( h h Z=l' B. _ w for some i, where W = (W ) W for y the variable that entered in the basis corresponding to X i,. (Checking condition (8) represents an additional ratio test to maintain subprogram feasibility.) Update each S by eliminating the indexes of variables that generated columns no longer in the basis of the restricted master problem. Also, eliminate these columns from the restricted master problem. If condition (8) is not violated, then return to Step 2. Otherwise, for the subproblem i in which (8) has been violated, let the basic variable which

9 first goes to zero in (8) leave the key column i basis and, for X i', the variable entering the basis in the restricted master, let y enter the key column basis for i. 4. For every subprogram i, in which the key column basis has changed, let that basic feasible solution be the initial solution in (7). Check every column indexed in S for eligibility to enter the basis first. For each eligible column, pivot to the adjoining extreme point (or find an extreme ray) and add the associated column to the restricted master problem. (It will be shown below that all columns indexed in S and basic in the last restricted master are eligible to enter the basis.) Go to Step 3. In the next section, the equivalence of the key column strategy for decomposition and the first block strategy for basis factorization are shown. III. Main Results In the following discussion, it is assumed that the KCS and FBS use the same rules for entering and leaving variables among the sets of variables eligible in the two strategies and that the entering variable only depends on the sign of the reduced cost and the index of the variable (e.g., Bland's rule (Bland [27]), LRC rule (Cunningham [3])). In the proofs that follow, it will also be assumed that k = 1 and that the region Y = Y is bounded to ease the exposition. This can be done without loss of generality, and it enables us to drop the superscript i on all symbols associated with the subproblems.

10 The first result is that the initial step of each method is the same. Lemma 1. The strategies, KCS and FBS, follow the same solution path through the solution after the first new y variable (nonkey column) has entered the basis. Proof: We assume that each method starts with the same subproblem B basis, W. Until every x variable has a nonnegative reduced cost, FBS is solving the program min. cx (9) B BT B0 B0 s.t. Ax = b - T y x> 0, B0 B0 where y = (W ) h. The initial restricted master is Bn B0 0 min. cx + (q y )X B0 B0 0 s.t. Ax + (T y )X b (10) X0 =1 x > 0, so the same solution path is followed by FBS and KCS until a new column is chosen. Let Tr be the optimal set of dual variables found in (9) and (10), and let (q = T )((W ) ).- The entering variable y in FBS is chosen such that qs - T T s - W <. Cll) b, S, S

11 B0 If the leaving variable is some yr then W replaces a column in W B1 and W is obtained. FBS then solves min. cx (12) B1 B s.t. Ax = b - T y x > 0. If the leaving variable is some xr, then FBS solves min. cx + qsYs (13) B0 B s.t. Ax + T y = - T y.S x1' Ys 0, where B^ B -0 0 -1 qs q - q (W ) W.s and B BD T = T -T (W ) W In KCS. ys has the same reduced cost in the subprogram as (11) and is, therefore, eligible to enter. B0 1 Since Y is bounded, there exists some (W )1 W > 0. Let 1 1. *s max be the value attained by y in the adjacent basic feasible solution s reached by the simplex method. The new solution is y where B B BO y (i ) -Q Y (i) - (W ) W e, j basic in row i in W j_ **s max y(j) = 1 =therwi se 0 otherwise.

12 The restricted master program is then Bo x B 0 0 B0 B q (W0)-1 1 1 1 (14) min. cx+(q y ) (q Oy -q (W ) W 6 + q )X s max s max BB BB B B 00 0 0 01 1 1 1 s.t. Ax + (T y )X +(T y -T ) W T 0 )X =b ~s max *s max 0 1 x + X 1, x, X > 0. If condition (.8) is not violated, then the same solution as that in (13) is obtained. If condition (8) is violated, then X) is replaced by X1 and the same solution as in (12) is obtained. In this case, the basis B B0 B1 1 B0 W corresponding to y replaces W, and a new key column is correspondingly defined. Lemma 1 can be applied to any situation in which the algorithms agree on the same single key column (secondary block subbases in y). The next lemma proceeds by induction on the number of nonkey columns to show that KCS and FBS follow the same path. Lemma 2. The strategies, KCS and FBS, follow the same solution path until the secondary block subbasis in y is changed (the key column is replaced). Proof: We first show that if the secondary block subbasis is unchanged and the key column is not replaced, then the strategies follow the same path. We proceed by induction on the number of supplementary columns. Assume the hypothesis is true for any number of supplementary columns less than or equal to L. Lemma 1 gives the result for L=l.

13 Let the supplmentary column indexes be s,.., sL. FBS has just solved L min cx + E q y (15) -=l st S L B0 Bo s.t. Ax + T y =b - T y Q=l -st sQ x, y > 09,.. L, and KCS has solved BL B0 0 L o min. cx + (q )X + (q y + qs ) (16) k=l 9 max B B 0 L B b 00 00 9, s.t. Ax + (T y )X + Z (T y + T e )X =b, 9=1' s[ max 0 L X + X = 1 9=1 x, A; > 0, Q = 1,..., L. * * Let (x, y ) be the primal optimum found by FCS in (15) and let r, be the dual optimum. An equivalent basic feasible solution (x, X) can be found in (16) by letting * x = x = g/max = 1,... L, L Z N~ =1.- Z N, g-l where we note that X is basic according to the assumption. To * show complementarity, define a dual solution (iri,) in (16) by fi = Tr and ^ B0 BO Bo B0 a = q y - (T y ).

14 This implies that c - irA = c - i A, B00 0 BB q y - (T ) - a = 0, and Bo Bo B 0 - O B00 q y +q 0 -r TT 0 -a s max s max =(q - T T )m, L = 1,..., L. 3 *'s / max Hence, complementarity and dual feasibility hold in (16) and in (15) since e > 0, showing the equivalence of the optima of (15) and (16). max Note that this also implies that, whenever (15) and (16) have corresponding bases then the same set of reduced costs are negative, hence the same entering variable will be chosen by any rule that only considers the sign of the reduced costs and the indexes of the variables. Note also that for a basis Din (15), the constraints in (15) can be reduced to -1 x -1 NBB L B B I XB + D NxxN + D (T y ~)X + 1 (D(T y ~) 0+ I max L B0 B + E (D (T y ) + D T )ax = D b x DT=Ly) +1 IjR)max L' L ~+ T + = 1, Z=l Z=L +1 where Ix is the identity corresponding to basic variables in x, L of the supplementary variables correspond to basic variables in D, and the Qth supplementary variable is basic in row j (2). This can be further reduced to

15 L L ~ IxB + D Nx + Z I X + = b, x B N Z=l N9) Z=L +1 sz L X0 = C b1 -~1 b Z=l J()' where D. T G for i + j ( ), = 1,.., L ^i-*s! max D T - for i = j( ), = 1,..., L 1. ~ s 9max and Di' (b - T y'' =- 0 BO, = T D. (b - T y i + j,..., L D. (b - T y )/ = j(ma ), = 1 L Hence, -1 L b. i. s* max T -l B B B0 B0 0 is D (b - T y ), R J. so, the choice of leaving variable in (15) and (16) is the same for the same entering variable. A new column, y enters in FCS if q - T - P W.< 0,

16 * B0 B0 1B0 where p = (q - T )(W. This is again the reduced cost of B B B ys in the subprogram and we note that since a = (q - T T )y, then the value of the subprogram solution including ys must be less than a, showing that the column correspoding to ys can enter in (16). Since X remains in the basis by the assumption, the column corresponding to Ys can be placed in (16) incrementing L to L+l. The solution of the augmented restricted master in (16) will have an equivalent solution to the augmented problem (15) by the same reasoning as above. This completes the induction. The proof is completed by noting that if KCS leads to a key column replacement then (8) is violated for some X" that corresponds to the supplemental variable y. This is exactly the condition for the leaving column to be from the secondary block subbasis and, therefore, the secondary block subbasis will be changed. Similarly, if the secondary block subbasis is changed, then (8) would be violated in KCS and the key column would be replaced. Therefore, the two strategies lead to the same solution path until a key column (secondary block subbasis) replacement. The only remaining obstacle is to show that the solution paths will be equivalent after a key column is replaced. Lemma 3. The two algorithms are equivalent through the iteration B following the replacement of the secondary block subbasis W in FCS (the key column in KCS).

17 Proof: First, we check that the basis generating the new key column is the same as the new secondary block basis. In KCS, if X enters to force a key column replacement, the y replaces y. s J where B L _ L+ j = argmin {{(W ). h- i }/W L+ }, (17) 1 Z=2 is isL+1 W. > 0 is and A is the current value of X. In FBS, the leaving variable is chosen as yk where B L Bo 1 Lk = argmin {{(W ) h - I W y }/W. }. (18) ih- Z-2Wis z sz isL+1 IS W. > 0 is The result that i = k is clear since X = y sz Let the new subprogram basis be B1 and let L-l supplemental columns (labeled Z = 2,..., L) be basic. The L-l supplemental columns that were in the previous restricted master problem can be written as 1 1 _ - q y + q 6. + q 6s................ - - k - z -(19) B B 1 1 B _ T y + T. +T e * S j's S L ~~1 B1 Z where T and T are now found relative to W and 8. and 0 are the ~sj's j S values of yj and Ys, respectively in the corresponding subprogram solution. The new restricted master problem is found by adding columns for the new supplemental variables prescribed by the algorithm as

18 B1 B1 1 L B3 1 9 P (20) min cx + Cq y 1 + c q y + q9x (.20) Q=2 9 B1 B L B1 B ) s.t. Ax + (T y )X + (T y + T ) =b, 9=2 es 1 L X + Z X = 1, 9=2 x, X > 0, 2 = 2,..., L 9h B where e is the value of y in the solution adjacent to y The equivalent FBS problem is L min cx + Z q y (21) 9=2 Q S L-B1 B1 s.t. Ax + E T y = b - T y 9=2 9s 9 x, y > =, =..., L. If system (20) is initiated with the basic supplemental columns that were in the previous restricted master problem's basis, then (20) and (21) have the same initial solution. Note that for 7r the dual vector corresponding to the first basis in (21) and for B1 B1 B 1 B1 = q y -7T y, then q s - TT, > 0, (22) s. J's.j j since yj just left the basis in the FBS problem. Therefore, every column (19) would have a positive reduced cost in problem (20) relative to the new basis. Hence, it is justifiable to discard these columns from the basis.

19 Lemmas 1, 2 and 3 lead to the following main result. Theorem. The strategies, KCS and FBS, follow the same solution path in solving linear programs with a block angular structure. Proof: By Lemmas 1 and 2, the strategies are equivalent if no key column is replaced. By Lemma 3, after key column replacement, the strategies obtain the same solution. This implies the two strategies are equivalent for all pivots. IV. Conclusion The equivalence of the FBS strategy for basis factorization and the KCS strategy for Dantzig-Wolfe decomposition shown here displays some differences and similarities between standard Dantzig-Wolfe decomposition and basis factorization in their approaches to solving structured linear optimization problems. By fully optimizing in the subprogram, Dantzig-Wolfe decomposition takes a larger step toward the optimum than that taken by a single pivot in the KCS strategy. Hence, initial convergence to an optimum may be faster. Difficulties may arise, however, if the new extreme point columns contain elements of columns not in an optimal linear program basis as in (19). The algorithm may require many iterations to eliminate all of these "contaminated" columns and obtain an optimum. The KCS strategy also suggests that some hybrid technique between basis factorization and decomposition may be possible. If some notion of a key column is maintained, it may be possible to determine whether wholesale replacement of "contaminated" columns is

20 reasonable in order to speed convergence and maintain accuracy.

References [1] J. R. Birge, "The relationship between the L-shaped method and dual basis factorization for stochastic linear programming," Department of Industrial and Operations Engineering, The University of Michigan, Technical Report 82-15 (Ann Arbor, 1982). [2] R. G. Bland, "New finite pivoting rules for the simplex method," Mathematics of Operations Research 2 (1977) 103 - 107. [3] W. H. Cunningham, "Theoretical properties of the network simplex method," Mathematics of Operations Research 4 (1979) 196 - 208. [4] G. B. Dantzig, "Upper bounds, secondary constraints, and block triangularity in linear programming," Econometrica 23 (1955) 174 - 183. [5] G. B. Dantzig and P. Wolfe, "The decomposition principle for linear programs," Operations Research 8 (1960) 101 - 111. [6] A. Geoffrion, "Elements of large-scale mathematical programming, Part I:Concepts," Management Science 16 (1970) 652 - 675. [7] M. J. Kallio, "On large-scale linear pgoramming," Systems Optimization Laboratory, Stanford University, Technical Report SOL75-7 (Stanford, 1975). [8] C. Winkler, "Basis factorization for block-angular linear programs: unified theory of partition and decomposition using the simplex method," Systems Optimization Laboratory, Stanford University, Technical Report SOL74-19 (Stanford, 1974).