FINDING MAXIMUM FLOWS IN NETWORKS WITH NONZERO LOWER BOUNDS USING PREFLOW METHODS Tongnyoul Yi and Katta G. Murty Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report 91-21 July 1991

Finding Maximum Flows in Networks with Nonzero Lower Bounds using Preflow Methods Tongnyoul Yi and Katta G. Murty Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117, U.S.A. July 1991

Abstract There are methods such as preflow methods(for example, the preflow push algorithm by Goldberg and Tarjan[2, 3]) which can be used directly to find maximum flows only in networks with zero lower bounds. We describe a simple two phase approach for finding a maximum flow in a network with nonzero lower bounds, using such an algorithm.

Let G = (/, A, Q, k, s, t) denote a pure directed single commodity flow network with AX = set of nodes; A = set of arcs; ~ = (iij), k = (kij), the vectors of lower and upper bounds(upper bounds are also called capacities) for arc flows in G satisfying <- kA, e: 0; 5, t, the source and sink nodes in G. A feasible flow vector f = (fij) is a vector of flow fij defined over arcs (i, j) E A satisfying e < f k k(1) 0, if i s,t f(i,)- f( i)= v, if i=s (2) [ -v, if i = t where for any i E K/, f(i,A) = sum of fij over j such that (i,j) e A and f(YA, i) = sum of fji over j such that (j, i) E A. The maximum flow problem in G is to find a feasible flow vector with the maximum possible value. The conditions (1) are the bound constraints. (2) are known as the flow conservation eqations. If there are two or more parallel arcs joining the same pair of nodes in G, they can all be combined into a single arc with the same orientation, with bounds obtained by summing up the bounds on the combined arcs. So, without any loss of generality, we assume that there are no parallel arcs in G. There is one significant difference between networks with zero lower bounds, and those with nonzero lower bounds. If the lower bound vector is zero, there is always a feasible flow vector, since the vector 0 is itself feasible. If the lower bound vector is nonzero, it is possible that there is no feasible flow vector. There are a class of methods for the maximum flow problem in networks with zero lower bounds based on preflow. A preflow is a vector defined on A satisfying (1); and (2) as ' inequalities for i 5 s or t, instead of equalities as required. An example of this type of method is the recently developed preflow push algorithm due to Goldberg and Tarjan [2, 3]. These methods obtain a sequence of preflows and terminate only when the preflow becomes a feasible flow vector, and at that time it will be a maximum flow. That is why they do not detect infeasibility directly, and are thus applied only for solving the maximum flow problem in networks with zero lower bounds. In this note we develop a simple two phase approach for tackling the maximum flow problem in a network with nonzero lower bounds, using such an algorithm. Given a feasile flow vector f = (fij) in our network G, a path P from s. to t in G is said to be a flow augmenting path( FAP ) with respect to f if fij < kij for all forward arcs (i, j) on P fij > kij for all reverse arcs (i, j) on P 1

The classical result of Ford and Fulkerson[l] states that a feasible flow vector in a network is a maximum value flow if and only if there exists no FAP from the source to the sink with respect to it. This result is the one most commonly used to check whether a given feasible flow vector is a maximum value one, and is the basis for several augmenting path methods for the maximum flow problem. Given a feasible flow vector f = (fij) in G, construct a set of arcs denoted by A(f) by the following rules: (i) for each (i,j) e A satisfying fij < kij, include the arc (i,j) in A(f) with a + label, lower bound 0, and capacity(or upper bound) kij = kij -fj. This + labeled arc (i,j) in G(f) is said to correspond to the arc (i,j) in G. (ii) for each (i,j) e A satisfying fij > eij, include the arc (j, i) in A(f) with a - label, lower bound 0, and capacity ij = fij - ej. This - labeled arc (j, i) in G(f) is said to correspond to the arc (i, j) in G. A(f) is called the set of residual arcs, and the network G(f) = (A/,A(f),O,i = (ij), s, ) is known as the residual network with respect to f. Notice that IA(f)l < 21AI, i.e., the number of arcs in the residual network is at most twice the number in the original network. Let Algorithm 1 refer to any algorithm such as preflow push algorithm which can process directly only maximum flow problems in netowrks with zero lower bounds. The two phase procedure for processing the maximum flow problem in our network G with lower bound vector ie 0 by Algorithm 1 is the following: Phase I Transform the problem of finding a feasible flow vector in G into that of finding a maximum flow in an augmented network G* in which lower bounds for all arc flows are zero, by well known classical techniques( See Ford and Fulkerson[1] or Murty[4, section 2.6] ). Solve the maximum flow problem in G* by Algorithm 1 directly. From this either conclude that there is no feasible flow vector in G and terminate, or obtain a feasible flow vector in it. Suppose a feasible flow vector f = (fij) of value v has been found in G. Go to phase II. Pase II Construct the residual network G(f) as described above. Since the lower bound vector in G(f) is 0 by definition, a maximum flow in G(f) from s to t can be found by Algorithm 1 directly, which do. To avoid confusion with flow vector in the original network G, we denote the maximum flow obtained in G(f) by g = (gpq), and its value by w. Lower bounds in the residual network G(f) are 0, and for a pair of nodes p, q, if there are arcs (p, q) and (q,p) both with positive flows in g, then the flows on them can be canceled(i.e., replace the larger of gpq, gqp by their difference and the smaller by 0) and at least one of these flows converted to 0, leading to 2

another feasible flow vector in G(f) of the same maximum value. We assume that this is done. So, without loss of generality, we assume that for any pair of nodes, the vector g has positive flows in at most one of the two orientations for arcs joining them. Define the flow vector f = (fi) in G, where for (i,j) E A (fij +.ij, if there is a + labeled corresponding arc (i,j) in G(f) with gij > 0 fij = f-'j - ji, if there is a - labeled corresponding arc (j, i) in G(f) with gji > 0 fij, otherwise Then f is a maximum value feasible flow vector in G and its value is v +w. Terminate. THEOREM The flow vector f obtained in Phase II of the above procedure is a maximum value feasible flow vector in G. PROOF Since f is a feasible flow vector in G of value v; and g is a feasible flow vector of value w in G(f), the fact that f is a feasible flow vector of value v + w follows from the flow conservation equations satisfied by f and g in the respective networks G and G(f), and the definition of upper bounds in G(f). Now, to show that f is a amximum flow in G, suppose not. Then there must exist an FAP from s to t with respect to f in G. Suppose it is P. We will now show that using P we can construct an FAP from s to t P1, in G(f) with respect to g. 1. If (i,j) is a forward arc on P with fij = fij, we have fij < kij, so arc (i,j) exists in G(f) with + label and capacity kij - fij > 0, and since fij = fij, we must have gij = 0. So put (i,j) as a forward arc on P1. 2. If (i,j) is a forward arc on P with fij > fij, form the definition of f, (i, j) must be a + labeled arc in G(f) with ij = fij - fij > 0, and since fij = fij + 9ij < kij, we have gij < kij - fij = iij. So put (i,j) as a forward arc on Pi. 3. If (i,j) is a forward arc on P with fij < fij, from the definition of f, (j, i) must be a - labeled arc in G(f) with gji > 0. Put (j, i) as a reverse arc on P1. 4. If (i,j) is a reverse arc on P with fij = fij, we have fij > ~ij, so arc (j, i) must be a - labeled arc in G(f) with capacity iji = fij - ij > 0, and from the definition of f, 9ji = 0. Put (j, i) as a forward arc on Pi. 5. If (i,j) is a reverse arc on P with fij > fij, from the definition of f, (i,j) must be a + labeled arc in G(f) with gj = fij - fij > 0. Put (i,j) as a reverse arc on P1. 3

6. If (i,j) is a reverse arc on P with fij < fij, from the definition of f, (j, i) must be a - labeled arc in G(f) with gji = fj - fi > 0; and since fij - gji = fij > ij, we have gji < fj - ej = /ji. Put (j, i) as a forward arc on P1. It can be verified that the path P1 constructed using statements 1 to 6 above is a path from s to t in G(f), with the forward, reverse orientations for arcs on it as specified in these statements, and that it is an FAP from s to t in G(f) with respect to g. This contradicts the hypothesis that g is a maximum value flow from s to t in G(f). So there does not exist any FAP from s to t in G with respect to f. Hence f is a maximum value flow in G. I The theorem shows that the two phase procedure described here always finds a maximum flow in the given network G. References [1] L. R. Ford Jr. and D. R. Fulkerson, 1956,"Maximum Flow through a Network", Canadian Journal of Mathematics, 8(399-404). [2] A. V. Goldberg and R. E. Tarjan, 1986, "A New Approach to the Maximum Flow Problem", Proceedings of the 18th Symposium on the Theory of Computing, (136-146). [3] A. V. Goldberg and R. E. Tarjan, 1988, "A New Approach to the Maximum Flow Problem", Journal of the Association for Computing Mafchinary, 35, no. 4(921-940). [4] K. G. Murty, 1992, Network Programming, to appear. 4