STUDIES OF LEXICOGRAPHY IN THE GENERALIZED NETWORK SIMPLEX METHOD Jose C. Arantes Department of Mechanical, Industrial and Nuclear Engineering University of Cincinnati Cincinnati, OH 45221-0072 John R. Birge and Katta G. Murty Department of Industrial & Operations Engineering University of Michigan Ann Arbor, MI 48109-2117 Technical Report 92-12 January 1992

STUDIES OF LEXICOGRAPHY IN THE GENERALIZED NETWORK SIMPLEX METHOD Jose C. ARANTES Department of Mechanical, Industrial and Nuclear Engineering, University of Cincinnati, Cincinnati, Ohio, 45221-0072, USA and J. R. BIRGE and K. G. MURTY Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117, USA Abstract This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can help us to understand and extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exists negative multipliers. Second, we developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive and negative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step is O(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence. Key words: linear programming, generalized networks, simplex method, degeneracy, lexicography, cycling 1. Introduction Let G = (N, IA) be a directed connected generalized network (GN) with N = set of nodes, A = set of arcs, where IN I = n, IAI = m and A may contain self-loops at some or all the nodes. Unlike in pure networks, flows in GN are subject to a linear gain or loss as they travel through the arcs, i.e., if a flow of fi, units enters an arc (i, j) at its tail node i, it becomes Pijfij units by the time it reaches the head node j; the factor pij is known as the multiplier associated with arc (i, j); and fi is known as the flow in arc (i, j) or the flow variable associated with it. The general problem, known as the generalized minimum cost flow problem (GMCF) on G is 1

2 Minimize E cjf (ij)EA - fij + Pjifji = bi, i (1) j:(i,j)eA j:(j,i)er o < fij< u (i,j)E A The coefficients of fij, for (i, j) E A and i ~ j, are -1 and pij respectively in the constraints in (1) corresponding to nodes i and j. The coefficient of fi, for the self-loop (i, i) E A, appears in only the constraint in (1) corresponding to node i, we assume that its coefficient there is scaled to be either -1 or +1; the self loop is said to be slack (surplus) self-loop depending on whether this coefficient is +1 (or -1). The multiplier associated with any self-loop is by definition +1. In (1), bi is the requirement at node i. The variables fii in (1) associated with self-loops in G, represent slack or surplus variables associated with the requirement constraint at i E N. Currently, variants of the primal simplex algorithm implemented using the rooted loop labeling data structures to represent the quasitrees in the basis network [2, 4, 6] are among the most efficient practical algorithms for solving the GMCF. Similarly to pure network flow problems, GN problems tend to be usually degenerate. The strongly convergent (SC) primal simplex algorithm of Elam, Glover and Klingman [2] resolves the problem of cycling under degeneracy in the GMCF. However, as pointed out by them, the SC algorithm works only when all the multipliers are positive. The equivalence between strong convergence and lexicography has been established by Partovi [8] and Orlin [7]. In this paper, we develop an efficient implementation of lexicography for solving GMCF with multipliers of arbitrary signs. This implementation requires, in each pivot step, the same worst case effort as the SC rules. The following section presents some results on the the basis inverse. Section 3 introduces the ratio matrix R and presents an approach, based on R and lexicography, for

3 selecting the dropping arc in GN with multipliers of arbitrary sign. This approach requires the same effort as the SC rules. Section 4 presents some concluding remarks. 2. Results on the Basis Inverse Since (1) is a GMCF, there are no redundant equality constraints in (1), see [2, 4, 6]|. A basic solution for (1) corresponds to a partition of arcs in A into (Q, L, U), where Q: = set of basic arcs in this partition, satisfying IQI = n, and the column vectors associated with arcs in Q forming a nonsingular square submatrix B of order n of the coefficient matrix A of (1). The nonbasic arcs are partitioned into L, U which are respectively the sets of nonbasic arcs on which the flow is equal to the lower bound and capacity respectively. B is known as the working basis associated with the partition (Q, L, U). The basic solution of (1) corresponding to the partition (Q, L, U) is obtained by fixing the flows on the arcs in L (U) at their lower bound (capacity) and then evaluating the flows on the remaining basic arcs so as to satisfy the equality constraints. The partition is said to be primal feasible if the flows on basic arcs satisfy the lower and upper bounds. The basic arcs in Q in a partition (Q, L, U) form a spanning subgraph of G, with one or more connected components, each of which is a quasitree, i.e., a tree with one additional arc which may be a self-loop. So each quasitree contains a cycle which may be a self-loop. In rooted loop labeling, node labels are defined in each quasitree separately. If the cycle in a quasitree is a self-loop it is considered to be a forward (reverse) arc if it is a slack (surplus) arc, and it is the unique root node for the quasitree. If the cycle in a quasitree is not a self-loop, then an arbitrary predecessor direction is selected for it, and the in-cycle arcs are classified as forward or reverse accordingly. When the cycle arcs are deleted from a quasitree, it is obtained a node disjoint collection of trees called its tributary trees. Each tributary tree contains exactly one cycle node which is its root node. Arcs in the tributary trees are classified as forward arcs if they are directed away from the root node, reverse otherwise.

4 Let S be a subset of Q. FOR(S) and REV(S) denote the sets of forward and reverse arcs in S. The labelling of nodes is such that, if (i, j) e FOR(Q) then i is a predecessor of j; i is a successor of j otherwise. The collective gain/lossfactor of S, X(S), is defined to be nPij J(S) = (i,je REV(S) nPij (i, j) E FOR(S) where II pi is defined to be +1 if S = 0. (i. j) S The predecessor path of a node g in a quasitree, denoted by Tg (the same symbol will also be used to denote the set of nodes or the set of arcs on it) is obtained by a trace of the predecessor indices beginning with g, and terminates when a node repeats. So Pg repeats no arcs, and always contains the cycle or self-loop in the quasitree containing g. The symbol Pig denotes the portion of the predecessor path of g up to node i if i is an ancestor of g, or the empty path otherwise. Let B be the basis associated with a partition (Q, L, U). Since rows, columns of B are associated with nodes in N, arcs in Q respectively; rows, columns of B'1 are associated with arcs in Q, nodes in N respectively. Let P.(k) = column of B'1 associated with node k, PI.) = row of B'1 associated with arc (i, j) E Q and /Pt1k) = entry in B-' in row associated with (i, j) E Q and column associated with node k. Then Bp.(k) = I.,k the kth column vector of the unit matrix of order n; i.e., 8.(k) is the vector of flow values on the basic arcs in Q to satisfy a requirement of one unit at node k and zero units at all other nodes, with zero flows on all nonbasic arcs. From this we see that,i.tk) 0 iff (i, j) E k. Actually, see [2, 6], iji(k)= 60CV(Pik), (2)

5 where6= 0 if (i, j) 0 ~Pk, +1 if (i,9 j) E FOR(~Pk), or -1 if (i, j) E REV(~Pk); CC = [ VyCk)Y if (i, j) is on the non-self-loop cycle Ck in the quasitree containing node k, or 1 otherwise. Result 1 follows from (2). Result 1: For (i, j) E Q and k E N, I31/1k) = 0 if (i, j) o ~Pk; /3k/k) ~ 0 otherwise. Result 2: From the above, if p, q are any pair of nodes in the same quasitree containing an arc (i, j), then /3i/P) and /3l/q) are both nonzero iff (i, j) E PP n ~P, and X~p /() 'YQpxq) if x #y and (i, j) E P or x =y and (i, j) E P NiQP '~) /3j(q) if x #y and (i, j)er ~Px X(Pyq) UX where x= the node in P such thatUPxp =!Pp\Pq,y = the node in P'q such that P~yq = Pq\Ppj, See figure 1. Note that nodes x and y are only defined when nodes p and q belong to the same quasitree. These results follow because W(PVLp) =,W(~PxpxV) and iy(~Liq) = XIf(Pxq)VI(~Pix) if either x = y and (i, j) = ~Px or if x ~ y and (i', j) e- Py,, 'V(P'i) = V(Y)V(ijJ~y) and V~i4(Eq)= N%.IJPyq)V~(~Liy) if x ~ y and (i, j) EiPy node x q 6 (c) x #yand (i,j) E!P. (a) x #yand (i, j) e Pvx (b) x= yand (i, j)e =Px Figure 1: Different relative positions of nodes p and q and (i, j) e-P Pq

6 Result 2 directly leads to the following result Result 3: If pij > 0 for all (i, j) E Q then all nonzero entries in each row of = B'1 have the same sign. This result may not hold if pij < 0 for some (i, j) E Q. 3. Results on the Ratio Matrix and the Lexicographic Rules Let (Q, L, U) be the feasible partition associated with the basis B, and (p, q) be the entering arc in some pivot step. Let f = (fi: (i, j) E A) be the basic feasible solution (BFS) associated with (Q, L, U). In this section p, q always refer to nodes on the entering arc in the pivot step. Let (aij: (i, j) E Q) be the basis representation of (p, q), i.e., (ajj) is the pivot column (or the updated column of the entering variable) in this pivot step. Let A,(p), P.ij(q) denote the entries in B-' in the row associated with (i, j) e Q, and the columns associated with p, q. The value of aij, for (i, j) E Q, can be obtained by: _-Pi(p) + ppq /io4q) if p ~ q aij = P(p) if p = q and (p, q) is a slack self-loop (3) -Pj(p) if p = q and (p, q) is a surplus self-loop When it is primal feasible, the partition (Q, L, U) is said to be lexico primal feasible, see [5], if p/i/) is lexicopositive (> 0) for (i, j) Q satisfying f j = 0 and,fj(.) is lexiconegative (-< 0) for (i, j) E Q satisfying fij = uij. The bounded variable lexico simplex method [5] is initiated with a lexico primal feasible partition, and executed using a special dropping arc choice rule called the lexicographic rules, in each pivot step, to guarantee preservation of the lexico primal feasibility property. Let D denote the set of all the arcs in Q u {(p, q)} eligible to be the dropping arc in this pivot step, see [2, 4, 6]. If D is a singleton then the dropping arc is identified unambiguously. However, if IDI 2 2 then the lexicographic rules obtains the dropping arc (r, s) as follows:

7 Lexicographic Rules: The dropping arc in this pivot step is (p, q) iff either (p, q) E 1 1 L n D and ( —),//.) > 0 for all (i, j) E D n Q, or (p, q) E U n D and (I —) 0(.)< 0 aij aij for all (i, j) E D n Q. Otherwise, the dropping arc is (r, s) E D such that either (- ) frs(.) ars 1 1 1 = lexicomin {( — -) /i(.): (i, j) E D n Q} if (p, q) e L or (-1) Irs(.) = lexicomax {((-) aij ars aij A/(.): (i, j) D nQ} if(p,q) U. Notice that, from (2) and (3), aij ~ 0 iff (i, j) E Pp u Pq, and for carrying out the lexicographic rules, we need the rows (-) Pij(.) for each (i, j) E D. For this reason and aij since D is a subset of p u q, see [2, 6], we define a matrix, called the ratio matrix, whose rows correspond to arcs (i, j) E p u Pq and whose columns correspond to nodes k E N. Define Rij(k) = ik) for (i, j) E Pp u Pq, k = 1 to n (4) aij and let R denote the matrix (Rj(k): (i, j) E Pp u rPq in some order, k = 1 to n). We verify that both f,/3(k) and Rij(k) are zero for (i, j) E (tp u Pq)\Pk. For each k E N, let R.(k) denote the column vector (Rij(k): (i, j) E Pp u Pq). Also Rij(.) denotes the row vector (Rjl(k): k = 1 to n). It is straightforward to verify that R.(k) is a zero vector if k is not a node in the quasitrees containing nodes p or q. There are four different cases to consider, these are Case 1: p ~ q, p and q belong to different quasitrees in the basis network (N, Q). Case 2: p ~ q, p and q belong to the same tributary tree in a quasitree in (N, Q). Case 3: p ~ q, p and q belong to different tributary trees in the same quasitree in (N,Q). Case 4: p = q, (p, q) is a self-loop. We consider each case separately.

8 Case 1: p ~ q, p and q belong to different quasitrees in the basis network (N, 0). Let TPand Tq refer to the quasitree containing node p and q respectively. We will use and Tq to also denote the set of nodes on these quasitrees. In this case -a= -fi()= - 6cxxyQPj,) if (i, j) EP, where 6, cz are defined as in (2) for k = p; and -aj= Ppq /3ij(q) = PPq60C XVfQi~q), where 6, cc are defined as in (2) for k = q. From these facts and (4) we have 0 if ke lW \(Tp'J Tq) and (i, j) r (~Pp u Pq) R1j(k) = Ai(k) Ppqpqij(q) if k ETP and (i, j) ~Pp if ke~~qand (i, j) e=Pqand Let g denote either node p or q and hp = -1,9 hq = Ppq' From above and from (2) we verify that:- for (i, j) e- ~Pg,, k E ~Pgq Rij(k) = 0 if (i, j) C ~Pg\~Pk, Rij(k) =- Pk)if (i, j) P'k)Tk and R..(k) = X(Cg i ij)-Pkr-CgwheCg ithcycle in the quasitree kg' ~~~hg'f(~tig) i i )e~k ~C~weeCi h conftaining node g. See figure 2(a). node k node k node g node g (2a) k c-P9 Arcs (5) and (6) 0 ~Pkg Arcs (1), (2), (3) and (4) e- ~Pkg (2b) k ofPg Arcs (l)and (2)e EPwg and arcs (3), (4), (5) and (6) o fPwg Figure 2: Subcases of Case I resulting of different relative positions of nodes k and g.

9 For g = p or q and k e Tg\Pg, define w to be the first common node on g and Pk. So Pw = Pg n Pk. For k e Tg\Pg, Rij(k) = 0 if (i, j) e Pg\Pk, Rij(k) = - k) if (i, j) e Pwwg hgN(fPwg),and Rij(k)= -(Cg)Pwk) if (i, j) E Pg n Cg. See figure 2(b). Hence we have the hgV/(Pwg) following result Result 4: For g = p or q and k E Tg\Pg, let w to be the first common node on fPg and Pk. Then, R.(k) = V(Pwk) R.(w). Result 5: Let g = p or q. Let k E Pg, and Cg be the loop in the quasitree of g. If k E fPg\Cg, Rij(k) has the same value (= ) for all (i, j) E Pk. If k E Cg, then Rij(k) hgf(Pkg) has the same value (= (C ) for all (i, j) E Pkg rn Cg; and a different but the same value hgW!(Pkg) (= -—. ) for all (i, j) E Cg\Pkg. This follows from above. hgNf(Pkg) Using these results, we are now ready to discuss how to implement the lexicographic rules for selecting the dropping arc from the set D of eligible dropping arcs in this pivot step. This requires finding the lexicomin or lexicomax among rows Rij(.) of the ratio matrix for (i, j) E D. Recall that all arcs in D belong to p u Pq. Let N be the set of nodes contained in the quasitrees of p or q. For this computation we need to consider only columns of the (Rij(k)) matrix for k e N, since Rij(k) = 0 whenever k 0 N. The work required is to examine the columns R.(k) for k E N in serial order. In each column we have shown, see Result 5, that there are at most two distinct nonzero entries and, for every k E Pp u Pq, each of these nonzero entries can be computed by performing a division and a multiplication operations using the collective gain\loss factors of paths along p, fPq that were already obtained as a byproduct during the computation of the pivot column. Thus, to perform the comparison for finding the min or max among rows corresponding to (i, j) E D, in each column R.(k) for k E Up u q,, takes at most a constant

10 amount of work (three multiplications, divisions; and three comparisons). For k E N\(p u q), let w be the first common node of Pk with Pp u Pq as defined earlier. By Result 4, the column R.(k) is V(PWk) R.(w) and the comparisons for finding the minimum or maximum in this column among rows corresponding to (i, j) E D, needs only the sign of V(QPWk) beyond the entries in R.(w) which were already obtained above since w E p u Pq. For this we define sgn(k), for each k E N\(Pp u Pq), to be the sign of (Pwk). We show that sgn(k) can be computed for all k E N\(p u ~Pq) with a total of at most O(n) effort. First consider the quasitree of p. Let NI be the set of nodes in this quasitree not in Pp. For each node a E N1 adjacent to Pp (i.e., there exists an arc (a, d) joining a and a node d on ~P) make sgn(a) = sign of the multiplier of (a, d). Now find a node a, in N1 whose sign is not determined yet, but which is connected by an arc, say (a,, a0), to a node ao E N1, whose sign is already determined. Make sgn(al) = (sgn(ao))(sign of the multiplier of (a1, a%)). Repeat in the same way until sgn(a2) is determined for all a2 E N.. Then do the same for the quasitree of q. This whole work requires examining each of the arcs in (Tp u Tq)\Pp u!Pq) once, and hence takes at most O(n) effort. Case 2: p ~ q, p and q belong to the same tributary tree in a quasitree in (N, Q). Let T refer to the quasitree containing p and q. We will use T to also denote the set of nodes on this quasitree. As defined earlier (see Figure 1) x here denotes the first common node on p and Pq. Note that x is also a node on the same tributary tree of p and q. Here let g denote one of the three nodes p, q or x. Let hp = -1, hq = ppq, hx = -(Pxp) + pq V(Iq). For each (i, j) E Pp u Pq, associate the node g to be p if (i, j) E Pxp, q if (i, j) E Pxq, and x if (i, j) E,. Then, as before, for (i, j) E Pp u Pq, and for k E N, 0 if kE N\T Rij(k) = fik) if k e T and g is the g-node associated with (i, j) hgfi/g)

11 Note from (3) and (4) that hgfijg) = -PI3p) if(i, j) E P7 = PpqflJq) if (i, j) r Pxq, and equals -Pi/p) + Ppqflij(q) if (i, j) e P. From above and (2), we obtain the following: 0 if k E N and (i, j) E (PpP u P)3Pk -1 if k E ~P and (i, j) E P 1 if k E Pxq and (i, j) E~P Ppq'V&Pkq) R,~(k) = if k ET p U Pxq and (i, j)E Px hx 1 if kE ~Pand (i, j)E rPP\1'\ if k E~Pxand (i, j) E -Pkx n C It is straightforward to verify the following result corresponding to Result 4 under Case 1. Result 6: Let k e ThQPp u ~Pq). Let w be the first common node on P u Pq and PkV. Then, R.(k) = 14JPwk) R.(w). From these results we know that the number of distinct nonzero values in the column R.(k) for each k e3 N is at most two in this case. Using this and the same arguments as in case 1, the lexicographic rules can be implemented in this case also with at most 0(n) effort. Case 3: p ~ q, p and q belong to different tributary trees in the same quasitree in (N,Q).

12 Let T refer to the quasitree containing p and q. We will use T to also denote the set of nodes on this quasitree. Nodes x and y are as defined in Remark 1 (see Figure 1). Note that x (y) is the root node of the tributary tree containing node p (q). Let hp = -1)h p, hx= Ajf(~Px) + Ppq '4IQPxq)') and hy = AJq(Pyp) + Ppq VI(~Pyq). From (2), (3) and (4) we obtain: 0 if k =N and (i, j) e(!PpWPq)\Pk Rij(k) = -1 1 PpqW(VQkq) XV(Txk) 1 hxlf(~Pkx) 1 hxV(~Pky) hV qfP) if keT=,,pand (i, j) E P if k e=Pyq and (i, j) E P'yk if ke~-Pxp, U~Pyq and (i, j)c:P~, if k E~Pxp WPyq and (i, j) E P,, if k E Py. and (i,j) E6Pyk if kE P~,, and (i, j) E P if k e kec if kec kec Pyand (i, j) C P and (i, j)er P and (i, j)ec Pyand (i, j)ec Pyxor xyor ~Pk-y V~iC) Again, similarly to case 1, if we obtain the equations for R~~(k) for k E T\QP1, u Pq), it is straightforward to verify the following result corresponding to Result 4 under Case 1. Result 7: Let k E T\QP1, u ~Pq). Let w be the first common node on PU fPq and Pk. Then, R.(k) = 1If(~Pk) R.(w).

13 From these results we know that the number of distinct nonzero values in the column R.(k) for each k E N is at most three in this case. Using this and the same arguments as in case 1, the lexicographic rules can be implemented in this case also with at mos O(n) effort. Case 4: p = q, (p, q) is a self-loop Let T refer to the quasitree containing p and q. We will use T to also denote the set of nodes on this quasitree. In this case aij = -f/P) if (i, j) E Pp and (p, q) is a surplus selfloop; and aij = f3j(P) if (i, j) ePp and (p, q) is a slack self-loop. Let hp = -1 or +1 depending on whether the entering arc is a surplus or slack self-loop. From these facts and (4), 0 if k E N\T and (i, j) E P Rij(k) = J3fik) if ke Tand (i, j)E p hpli/p) Let C be the loop in T, different from the self-loop (p, q). From above and from (2) we verify that: 0 if k N and (i, j) E Pp\Pk Rij(k) = if kE Pp and (i, j) E k\Pkp hpN(QPkp) if k E Cand(i, j) e kp nC hpW(kp) Again, it is straightforward to verify the following result corresponding to Result 4 under Case 1.

14 Result 8: Let k E T\Pp. Let w be the first common node on Pp and Pk. Then, R.(k) = (Pwk) R.(w). From these results we know that the number of distinct nonzero values in the column R.(k) for each k E N is at most two in this case. Using this and the same arguments as in case 1, the lexicographic rules can be implemented in this case also with at most O(n) effort. 5. Conclusion and Extensions This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained help us to understand and extend the existing theory. First, it is verified that all nonzero entries have the same sign in each row vector of the basis inverse for a generalized network problem with positive multipliers. However, this property does not necessarily hold when there exists negative multipliers. Second, we developed a special implementation of the lexicographic rules for the GN simplex algorithm when addressing GN problems with positive and negative multipliers. This strategy evidently avoids cycling and, unlike the SC rules, it requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step is O(n) in the worst case analysis. This worst case computational effort is the same as that required by the SC rules for selecting the dropping arc in the method of strong convergence. This is an improvement since classical implementations of the lexicographic rules requires an worst case effort of order O(n2). The following extensions will be explored in a subsequent paper. First, due to the special characteristics of the matrix R from Section 3, the comparisons mentioned above can be performed if one knows only the signs of the elements to be compared. Hence,

15 although the actual values are obtained without any additional work, they are not really necessary. Simple rules can be introduced so that the comparisons can be realized by using only the sign information. More efficiency can be expected since comparing boolean variables requires less effort than comparing real ones. Moreover, memory requirements should decrease. Second, the matrix R allow us to develop a constructive proof of the equivalence between the strongly convergent and the lexicographic rules. This approach is more enlightening than existing methods for showing this equivalence. 6. Acknowledgement This material is based upon work supported by the National Science Foundation under Award N2 EECS-885101 and by the Brazilian Council for the Development of Science and Technology - CNPq under Award N- 20.2911/85. References [1] J. C. Arantes, Resolution of Degeneracy in Generalized Networks and Penalty Methods for Linear Programs, Ph.D. Dissertation, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor (1991). [2] J. Elam, F. Glover and D. Klingman, A Strongly Convergent Simplex Algorithm for Generalized Networks, Math. of O. R. 4(1979)39-59. [3] F. Glover, J. Hultz, D. Klingman and J. Stutz, Generalized Networks: A Fundamental Computer-Based Planning Tool, Mgmt Sci. 24(1978)1209-1220. [4] F. Glover, D. Klingman and J. Stutz, Extensions of the Augmented Predecessor Index Method to Generalized Network Problems, Transportation Science 7(1973)377-384. [5] K. G. Murty, Linear Programming (John Wiley & Sons, 1983). [6] K. G. Murty, Network Programming (Prentice Hall, 1992, to appear). [7] J. B. Orlin, On the Simplex Algorithm for Networks and Generalized Networks, Mathematical Programming Study 24(1985)166-178. [8] M. H. Partovi, A Study of Degeneracy in the Simplex Algorithm for Linear Programming and Network Flow Problems, Ph.D. Dissertation, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor (1984).