Transformations and Flow Decomposition

Flow Decomposition and Transformations Flow Decomposition and Transformations ‹ Flow Decomposition ‹ Removing Lower Bounds ‹ Removing Upper Bounds ‹ Node splitting ‹ Arc flows: an arc flow x is a vector x satisfying: Let b(i) = 6j xij - 6i xji We are not focused on upper and lower bounds on x for now. Flows along Paths Usual: represent flows in terms of flows in arcs. Alternative: represent a flow as the sum of flows in paths and cycles. 1 2 2 2 3 2 4 2 5 P 1 1 1 2 5 1 1 4 1 C 3 Two units of flow in the path P One unit of flow around the cycle C Properties of Path Flows Let P be a directed path. Let Flow(G,P) be a flow of G units in each arc of the path P. 1 2 2 2 3 2 4 2 5 Flow(2, P) P Observation. If P is a path from s to t, then Flow(G,P) sends Gunits of flow from s to t, and has conservation of flow at other nodes. Property of Cycle Flows ‹ If p is a cycle, then sending one unit of flow along p satisfies conservation of flow everywhere. 1 1 1 2 5 1 1 4 1 3 Representations as Flows along Paths and Cycles Let P be a collection of Paths; let f(P) denote the flow in path P Gij(P) = 1 if (i,j)  P Gij(P) = 0 if (i,j)  P Let C be a collection of cycles; let f(C) denote the flow in cycle C. Gij(C) = 1 if (i,j)  C Gij(C) = 0 if (i,j)  C Representations as Flows along Paths and Cycles ‹ Claim: one can convert the path and cycle flows into an arc flow x as follows: for each arc (i,j)  A xij = 6P  P Gij(P)f(P) + ‹ 6C  C Gij(C)f(C) We next provide an algorithm for converting arc flows to sums of flows around cycles and along paths, where each path is from a supply node wrt x to a demand node wrt x. Flow Decomposition Animation Flow Decomposition Notation: G = (N, A): the network x: Initial flow y: Flow at intermediate stage of the algorithm A(y) arcs with positive flow in y N(y) nodes incident to an arc in A(y) SupplyNodes(y) nodes with supply wrt y DemandNodes(y) nodes with demand wrt y P: C: paths with flow in the decomposition cycles with flow in the decomposition Flow Decomposition Algorithm Initialize begin y := x; P := ‡ ; C:= ‡; end Search(s, y) Carry out a depth first search starting with node s until finding a directed cycle C in G(y) or a path P in G(y) from s to a node t in DemandNodes(y). Select(s, y) begin if SupplyNodes(y) = ‡, then s  SupplyNodes(y); else s  N(y) end Capacities of Paths and Cycles 8 1 5 The capacity of C is denoted as '(C, y) = min arc flow on C wrt flow y. 4 5 4 9 7 7 2 '(C) = 4 C 3 -2 s 6 4 4 2 3 9 5 t P '(P) = 2 Let P be a path from s to t. The capacity of P is denoted as '(P, y) = min[ b(s), -b(t), min (xij : (i,j)  P) ] The decomposition algorithm begin Initialize while y z ‡ do begin Select(s, y) Search(s, y) if a cycle C is found then do begin let ' = Capacity(C, y) Add Flow(', C) to cycle flows Subtract Flow(', C) from y. end if a path P is found then do begin let ' = Capacity(P, y) Add Flow(', P) to path flows Subtract Flow(', P) from y. end end Flow Decomposition Animation Complexity Analysis ‹ Select initial node: z O(1) per path or cycle, assuming that we maintain a set of supply nodes and a set of balanced nodes incident to a positive flow arc ‹ Find cycle or path z O(n) per path or cycle since finding the next arc in depth first search takes O(1) steps. ‹ Update step z O(n) per path or cycle Complexity Analysis (continued) Lemma. The number of paths and cycles found in the flow decomposition is at most m + n – 1. Proof. In the update step for a cycle, at least one of the arcs has its capacity reduced to 0, and the arc is eliminated. In an update step for a path, either an arc is eliminated, or a supply node has its supply reduced to 0, or a demand node has its demand reduced to 0. (Also, there is never a situation with exactly one node whose supply is non-zero). Conclusion Flow Decomposition Theorem. Any non-negative feasible flow x can be decomposed into the following: i. the sum of flows in paths directed from supply nodes to demand nodes, plus ii. the sum of flows around directed cycles. It will always have at most n + m paths and cycles. Remark. The decomposition usually is not unique. Corollary A circulation is a flow with the property that the flow in is the flow out for each node. Flow Decomposition Theorem for circulations. Any non-negative feasible flow x can be decomposed into the sum of flows around directed cycles. It will always have at most m cycles. An application of Flow Decomposition Consider the problem of finding a shortest path from node 1 to all other nodes. Assume that all arc costs are non-negative. The model: Minimize ¦ (i, j)A Subject to ‹ ¦ j cijxij xij  ¦ j x ji R|n 1 if i 1 S| 1 if i z1 T Let x* denote the minimum cost flow. Then x* is the sum of flows of paths from node 1 to each other node, plus the sum of flows around cycles. A shortest path tree -1 -1 4 2 1 1 5 1 1 3 6 -1 4 3 -1 5 -1 The decomposition of flows yields the paths: 1-2, 1-3, 1-3-4 1-3-4-5 and 1-3-4-6. There are no cycles in the decomposition. Trees have no cycles. Other Applications of Flow Decomposition ‹ Reformulations of Problems. z There are network flow models that use path and cycle based formulations. z Multicommodity Flows ‹ Used in proving theorems ‹ Can be used in developing algorithms Transformations The minimum cost flow problem uij = capacity of arc (i,j). cij = unit cost of flow sent on (i,j). xij = amount shipped on arc (i,j) Minimize 6 cijxij 6j xij - 6k xki = bi for all i  N. and 0 d xij d uij for all (i,j)  A. If a constraint matrix (ignoring upper bounds) has at most one 1 and at most one -1 in each column, it corresponds to a network flow problem. Comment on Transformations Some transformations work directly with the LP formulations (system of equalities and inequalities) Others work directly on the networks Eliminating Lower Bound on Arc Flows Suppose that there is a lower bound lij on the arc flow in (i,j) Then let yij = xij - lij. Then xij = yij + lij Minimize 6 cijxij 6j xij - 6k xki = bi for all i  N. and lij d xij d uij for all (i,j) A. Minimize 6 cij(yij + lij) 6j (yij + lij) - 6k (yij + lij) = bi for all i  N. and lij d (yij + lij) d uij for all (i,j)  A. Then simplify the expressions. Eliminating Upper Bounds on Arc Flows The minimum cost flow problem Min 6 cijxij s.t. 6j xi - 6k xki = bi for all i  N. and 0 d xij d uij for all (i,j)  A. Before xij i After sij i ª1 0 º j «1 0» « » uij «¬ 1 1 »¼ Subtract constraint 3 from constraint 1 xij = bi = bj = uij j i LM 0 j M1 uij MMN 1 i sij 1 PO 0P 1 PPQ = bi - uij = bj = uij j Node Splitting 2 2 44 6 1 6 5 3 Flow x 4 Arc numbers are capacities 5 Suppose that we want to add the constraint that the flow into node 4 is at most 7. Method: split node 4 into two nodes, say 4’ and 4” 2 2 4’ 7 4” 6 1 5 3 5 4 6 Flow x’ can be obtained from flow x, and vice versa. Summary 1. Any feasible flow can be decomposed into the sum of flows around cycles plus the sum of flows from nodes with supply to nodes with demand. 2. Lower bounds that are not 0 can be replaced (via a simple transformation) with lower bounds that are 0. 3. Each upper bound on an arc can be eliminated, but it is at the expense of creating an additional node. 4. One can model constraints on flow into or out of a node by splitting the node