57. 74 1976L137 SLCO1 3376 Partitioning Generalized Upper Bounding and Angular Structures in Linear Programming by Johannes Bisschop and Alexander Meeraus ts Oz~ 1~E PMENT1" Technical Note No. 3 Research Project 670-24 July 1976 Development Research Center World Bank 1818 H Street, N.W. Washington, D.C. 20433 Partitioning, Generalized Upper Bounding, and Angular Structures in Linear Programming by Johannes Bisschop and Alexander Meeraus ABSTRACT: In problems with an angular structure, the initial basis is represented in reduced form via partitioning. If partitioning is also used in the updating of the basis, subsequent iterations do not differ from ordinary simplex iterations. 1. Introduction Special attention has been given to angular structures in linear programming in an effort to reduce the size of the working basis (see [3] and [5]). Chapter six in [6] gives an excellent discussion of Generalized Upper Bounding, and its generalization to block-triangular form. Such special linear programs with (m + p) rows are solved with a working basis that has size m , where m is usually much smaller than p . The result is a substantial saving in storage. The methods used, however, are a specialization of the simplex method, and require special implementation because of the increased complexity in updating the reduced working basis. In [2] we develop a compact updating proce- dure for the basis inverse that is unaffected by the size of the problem. For problems with an angular structure we will develop a representation of the basis inverse which is as compact as the reduced working basis discussed in [6] . The updating of the inverse basis, however, is done as in [2] The result is that our methodology takes advantage of angular structures - 2- without requiring a specialization of the simplex method for subsequent iterations. 2. Generalized Upper Bounding. Let b and a.i denote a set of m-dimensional column vectors, where i=1,2,... ,p , j=1,2,...,n , and p is large compared to m Consider the following class of linear programming problems. Minimize x00 subject to x00 x01 x012. . . x1 l22 23 . . . . . . xpl xp2 xp3 1 1 1 ...=1 1 1 1 . .. = 1 1 1 1 . .. =1 a00 a01 a02 . 111 a 2 a 3 2 2 2 . .3 . ap ap2 ap3 . . . b x ij 0 for all i and j Let Si , i=1,2,...,p , contain the variables xii , j=1,2,.. .ni Note that any basic feasible solution must include at least one variable from each set S . The initial basis B can therefore always be parti- tioned into the form I U = B V B Here i) The ith column of B , i=1,2,...,p , belongs -3- to a variable of the set Si ii) The p x p matrix I is an identity matrix, and is stored using pointers. iii) The p x m matrix U is a set of zero and unit vectors stored with pointers. iv) The mx p matrix V and mx m matrix B consist of selected columns from the last m rows of the original tableau. The inverse representation of B requires only knowledge of -1 I , U , V and Q , where Q = (B - VU) . If the last m rows of the tableau are sparse, then the matrix Q is sparse, as every column of Q is either a column of B , or a column of B minus a column of -V We refer to [1] where a compact representation of the inverse of a general sparse matrix is developed. Let x = (x1 , x2) , b = (bl , b2) , and c= (c1, c 2) Then Bx -b can be computed via i) x 2 Q-1 (b2 - Vb 1) ii) x 1 b - Ux2 and xB c can be computed via i) x2 = (c2- c1U) Q-1 ii) x l- x2V It is interesting to note that the matrix Q (B - VU) is exactly the reduced working basis developed in [6] . It is obtained by multiplying the initial basis B by a nonsingular transformation T of the form - T = 1 m I4- such that BT = [I 0 V B -VU -1 0p- and (BT) = . -.B - VU) V (6 - VU) In subsequent iterations the block-triangular form of the transformed basis BT is essentially maintained by updating the smaller matrix (B - VU) , although additional transformations are required. This is a serious disadvantage,,and results in extra computational cost. This additional cost is not incurred when the partitioning method is used. 3. Extension to Angular Structures. Generalized upper bounding techniques have a natural generaliza- tion to problems with angular structure. Assume that for i=0,1,2,...,p Ai is m0 x ni, x is ni x 1 , D is m x ni , and (x0 1 is the first component of x0 . Then consider the following class of linear programming problems Mimimize (x0 1 subject to D Ix b b1 92 x2 = 2 D x b p p p A0 x0 + A 1 + A2 x2 + . + A x = b xi > 0 for all i . - 5- Assume that the row rank of the matrices Di is mi . Then any basic feasible solution must include at least mi components of the vector x . The initial basis B can therefore always be partitioned into the form D UB B Let p = m. . Then 1 i=1 i) The i th block of columns in B , i=1,2,...,p corresponds to m components of the vector x . ii) The p x p matrix D is a block diagonal matrix consisting of p nonsingular blocks with dimensions (mi x mi) iii) The p x mo matrix U is a set of vectors which are either zero vectors, or vectors containing mi nonzero elements. iv) The mo x p matrix V and m0 x m0 matrix B consist of selected columns from the last m0 rows of the original tableau. The inverse representation of B requires only knowledge of D U , ad l where QOf=BB(BO D-1, , ad -1 , whr Q=( - VD-1U) ,and D-1 consists of p inverted blocks with dimensions (mi x m) . The (mo x mo) matrix Q is exactly the reduced working basis developed in 6]. Let the (p + m) - dimensional vectors x , b , and c be partitioned into (xl , x2) , (b1 , b2) and (cl c2) respectively. Then Bx = b is computed via i) x2 Q-1 (b2 - VD-1 b 1) iL) x = D-1 (b - Ux 2) -6- and xB = c is computed via i) x2 (c2 - 1 D-1 U) Q-1 ii) x1 = (cl - x2V) D-1 4. Conclusions. In large linear programming problems without an explicit structure, the initial basis is inverted using a structure detection algorithm such as the Hellerman-Rarick preassigned pivot procedure [4] . In problems with an explicit structure such as those with rectangular blocks, the initial basis is inverted by using first the explicit structure provided by the diagonal blocks, and then applying the Hellerman-Rarick algorithm to the reduced basis. Subsequent iterations are the same for both structured and unstructured problems if partitioning is used in updating the inverse basis (see [2]) . It is interesting to note that if the input to a linear program solver is a set of algebraic equations in set notation instead of a matrix, the angular structure (when present) can be detected via symbolic examination of the equations. References [1] Bisschop, J., and A. Meeraus, "A Recursive Form of the Inverse of General Sparse Matrices", DRC Technical Note # 1, 1976. 12] , "Efficient Updating of the Basis Inverse in Linear Programming via Partitioning", DRC Technical Note # 2 , 1976. 13] Danzig, G.B. and R.M. Van Slyke, "Generalized Upper Bounding Techniques", J. Computer System Sci. 1 (1967), pp. 213-226. [4] Hellerman, E. and D. Rarick, "Reinversion with the Preassigned Pivot Procedure", Math. Programming 2 (1971), pp. 195-216 . 15] Kaul, R.N., "An Extension of Generalized Upper Bounding Techniques for Linear Programming", Rept ORC 65-27 , Operations Research Center, University of California at Berkeley, 1965. [6] Lasdon, L.S., Optimization Theory for Large Systems, MacMillan Company: New York, 1970 .