Maximum Flow Networks Suppose G = (V, E)

Maximum Flow Networks Suppose G = (V, E)

Maximum Flow Networks Suppose G = (V, E) is a directed network. Each edge (i,j) in E has an associated capacity uij. Goal: Determine the maximum amount of flow between two specified vertices s and t. The capacity v of a path P is the sum of its constituent edge flows: v = xxij where xij is the flow from vertex i to vertex j. Applications to design: supply networks oil pipelines road traffic 1 Background Assumptions: Integer data Directed network Nonnegative capacities on each arc Vertex s is the source Vertex t is the sink Definitions: Residual network Cut Techniques: 1. Augmenting Paths Examine residual network for s-t paths. 2. Preflow-Push Flow moved according to individual edge not path. 2 Maximum Flow as Linear Programming Problem maximize v subject to x x ji 0 for each i s, t x

sj v x jt v ij j j j j 0 x ij u ij (i, j) E v 0 3 Example 2,4 2 3,9 s 1,2 8,8 3 4 2,6 4,7 t 7,9 Each edge is labeled as (xij, uij) = (flow, capacity). However, this flow value, v(x) = 11, is not a maximum.

4 Residual Network Given a current flow x, keep track of how much further the flow can be increased in each direction of the edge. For any edge in G: The corresponding edge (with capacities) in residual network of G: i xij, uij j uij -xij i j xij The residual network of G, G(x), has edges with positive residual capacity, rij = uij xij + xji. In general, it is the amount by which we can further increase flow from i to j in the current network. 5 Example Re-examined 2,4 2 3,9 s 1,2 8,8 3 4 3 4,7 2,6 t

7,9 Network with flows and capacities. s 2 1 6 1 2 3 2 6 8 4 2 4 2 t 7 3 Residual network with capacities. We know this network flow is not a maximum. How can we get a better one? What do we do in general? 6 Cuts A cut is defined by a partition of the vertex set E into subsets S and S* = E S. The cut [S,S*] consists of all edges with one endpoint in S and the other in S*. The forward edges of [S,S*] are denoted (S, S*). The backward edges are denoted as (S*,S). An s-t cut [S,S*] has s in S and t in S*. The removal of the forward edges in an s-t cut will separate vertices s and t. That is, there is no longer a directed s to t path. The capacity of any cut [S,S*], u[S,S*], is the sum of the capacities of the

forward edges of the cut. u[S,S*] is an upper bound on the amount of flow sent from S to S*. A minimum s-t cut has the smallest capacity among all s-t cuts. 7 Examples of 1-6 cuts 2 10 1 10 4 5 4 8 8 3 5 10 6 8 5 S={ } S* = { } Forward edges of [S,S*]= { } u[S, S*] = = 2 1 10 4

5 4 8 6 8 8 3 5 5 S={ } S* = { } Forward edges of [S,S*]= { } u[S, S*] = = 8 Theorems Theorem If x is any feasible flow and if [S,S*] is any s-t cut, then the flow value, v(x), from s to t is at most u[S,S*]. Corollary the max flow value the minimum cut capacity Max-Flow Min-Cut Theorem For any capacitated network, the value of the maximum s-t flow, x, equals the capacity of a minimum s-t cut, [S,S*]. v(x) = u [S,S*] 9 Improving a Flow Given the flow x, look for a path P from s to t in the residual network G(x) along which flow can be sent. Then send as much flow along P as possible. We call any directed path P from s to t in the residual network an

augmenting path. The residual capacity of such a path is (P) = min{rij:(i, j) P). To augment along P is to send (P) units of flow along each edge of the path. We then modify x and the residual capacities rij appropriately. rij := rij (P) for each edge (i,j) P rji := rji + (P) for each edge (i, j) P Result: flow value, v, increases by (P). 10 Example 2,4 2 3,9 1,2 s 8,8 4 3 4,7 2,6 t s 1 6 1 8 7,9 3

2 2 4 2 3 2 6 4 2 t 7 3 Network with flows and capacities. v Residual network with capacities. =11 Augment along path P = s-2-4-t. (P) = min{6, 2, 3} = 2. new flow value =13 4,4 2 5,9 s 8,8 1,2 3 4 2,6 5 6,7 t 7,9 s

2 1 4 1 8 1 2 6 3 4 4 6 2 t 7 11 Example Augmenting Paths Step 0: initial residual graph is original 2 6 1 4 8 2 8 4 2 4 3 6

2 3 5 1 5 5 4 2 2 3 4 2 1 2 4 1 5 3 2 8 4 3 2 3 5 2 6 6 5

6 Step 2: Push 5 units along path 1-3-5-6 2 6 5 5 Step 3: Push 2 units along path 1-2-5-4-6 4 4 4 3 6 Step 1: Push 4 units along path 1-2-4-6 4 4 1 5 4 2 3 3 2 1 1 5 6 4

2 5 2 6 5 Step 4: Push 1 units along path 1-3-5-4-6 12 Example continued 2 6 1 6 4 2 2 3 1 3 6 7 4 2 5 6 5 2 6 1 No more augmenting paths

8 4 4 8 2 3 6 2 3 5 5 6 2 6,6 1 0,2 6,8 4,4 2,2 3 4 7,8 3,3 5 6 5,5 6,6 Maximum Flow in G is 12

13 THEOREM The following are equivalent statements 1. 2. 3. The s-t flow x with value v(x) is maximum G(x) contains no augmenting path. There is an s-t cut [S,S*] with u[S,S*] = v(x) 14 Generic Augmenting Path Algorithm In this algorithm, we keep sending flow along augmenting paths until no s-t path exists in the residual network. Can carry out calculations entirely on G(x). Flows in G are found at the very end. algorithm augmenting_path; begin x := 0 while G(x) contains a directed path from s to t do begin P = Find_Path(s, t, G(x)); (P) := min{rij: (i,j) P}; augment (P) units of flow along P; update G(x); end; end; 15 Find_Path Options More than one way to pick an augmenting path Poor choices can lead to many augmentations.

Info lost when successive paths are found. Balance effort to find a good path with the reduction in # of augmentations. Maximum capacity select path P such that (P) is as large as possible. Shortest path use the path with the minimum number of edges. Scaling successively solve subproblems with a certain capacity. 3 50 50 1 1 50 4 50 2 16 Distance Labels For the shortest path version of the augmenting path algorithm and for another max flow algorithm, the pre-flow push, the notion of distance labels is needed. The distance label d(j) is a nonnegative integer assigned to each j in G(x). The distance labels are valid if d(t) = 0 d(i) d(j)+1 for each (i,j) G(x) If d(j) are valid, then d(j) is a lower bound on the shortest distance from j to t. If d(s) n then there is no s-t path in G(x). (n = number of vertices in G) An admissible edge in G(x) is one where d(i) = d(j) + 1. An admissible path is a path from s to t consisting of admissible edges and is a shortest

augmenting path from s to t. 3 1 4 5 2 17 Shortest Distance Algorithm Admissible paths are successively built by advancing until vertex t is reached. If no admissible edge is available at some point, then retreat and relabel will be a way of updating distances in the new residual graph. In this way, we maintain valid distance labels without starting from scratch. algorithm shortest augmenting path; begin x:= 0; calculate exact distance labels, d(j) to vertex t; j := s; while d(s) 0}; if E(j) with rjk > 0 empty then d(j) = n; if j s then j := pred(k);

end; algorithm augment; begin derive path P from pred; (P) := min{rij: (i,j) P}; augment (P) units of flow along P; end; 19 Example d(3)=1 3 4 1 5 d(1)=2 3 2 4 1 1 2 3 4 1 1 5 d(4)=0 3 2 4 1 d(2)=1

1. Calculate d(j) 3. Advance 1-2, retreat, relabel vertex 2 d(3)=1 d(1)=2 1 3 4 2 d(3)=1 5 d(4)=0 3 2 4 1 d(2)=1 2. Advance 1-2-4, (P) =1, augment d(1)=2 3 4 1 1 1 5 d(4)=0 3 2 4 1

d(2)=2 4. Advance 1-3-4, (P) =4, augment 20 Example d(3)=1 d(1)=2 3 4 1 1 4 1 3 1 d(3)=1 d(4)=0 4 d(1)=3 5 d(4)=0 2 1 1 2 3 4 1

2 4 1 2 d(2)=2 d(2)=2 5. Advance 1, retreat relabel 1 7. Advance 1, retreat, relabel 1 d(3)=1 d(3)=1 d(1)=3 3 4 1 1 1 3 4 d(1)=4 1 2 d(4)=0 4 1 d(2)=2 6. Advance 1-2-3-4, (P) =1, augment

3 4 5 d(4)=0 2 1 2 1 2 4 1 d(2)=2 8. Maximum Flow achieved 21 Example - Results 4,4 1 2,2 3 5,5 1,3 2 Note monotonicity of distance labels 4 1,1 Note monotonicity of path lengths 1-2-4 1-3-4 1-2-3-4 1 2

3 4 5 6 7 d(1) 2 2 2 2 3 3 4 d(2) 1 1 2 2 2 2 2 d(3) 1 1 1 1 1

1 1 d(4) 0 0 0 0 0 0 0 22 Additional Exercises 18 3 22 25 17 11 1 source 13 4 1 source 9 10 2 11 5

8 21 5 6 8 sink 24 6 6 4 30 26 22 7 3 19 17 2 8 6 9 11 7 5 7 3

source 7 sink 4 3 1 2 1 1 4 1 3 2 5 2 2 1 7 6 sink 23 Preflow-push Algorithm Distance labels d(t) = 0; d(i) d(j) + 1 for each (i,j) in G(x) Excess flow e(i) = excess at each vertex for a given preflow Active vertices vertices with positive excess Admissible edges edges that satisfy the condition that d(i) = d(j) + 1 Preflow infeasible solution;

Algorithm strives for feasibility/optimality when all excess at sink and source algorithm preflow-push; begin preprocess; while network contains an active vertex do begin select an active node i; push/relabel(i); end; end; 24 algorithm preprocess; begin x := 0; compute the exact distance labels d(i) from s; xsj := usj for each edge (s,j) in E(s); d(s) := n end; algorithm push/relabel(i); begin if the networks contains an admissible edge (i,j) then push = min{e(i), rij} units of flow from vertex i to vertex j; else replace d(i) by min{d(j)+1: (i,j) in E(i) and r ij > 0}; end; 25 Example 1. Network G 2. preprocess: first residual graph Active nodes: 2, 3 Active nodes: e(1)=0 d(1)=2 e(3)=0 d(3)=1 e(3)=4 d(3)=1 3

3 5 4 3 1 2 4 1 e(4)=0 d(4)=0 e(1)=0 d(1)=4 5 4 3 1 2 4 e(4)=0 d(4)=0 1 2 2 e(2)=0 d(2)=1 e(2)=2 d(2)=1 26 Example Selected node: 2 Active nodes: 3 Selected node: 3

Active nodes: 2 3. Saturating push of 1 unit along 2-4; Relabel distance node 2 Active nodes: 3, 2 e(1)=0 d(1)=4 Active nodes: 2 e(3)=4 d(3)=1 e(3)=0 d(3)=1 3 3 5 4 3 1 4. Push of 4 units along 3-4 2 4 1 e(4)=1 d(4)=0 e(1)=0 d(1)=4 1 4 3 1 2

4 4 e(4)=5 d(4)=0 1 2 2 e(2)=1 d(2)=2 e(2)=1 d(2)=2 27 Example Selected node: 2 Active nodes: Selected node: 3 Active nodes: 5. Push of 1 unit along 2-3 6. Saturating Push of 1 units along 3-4 Active nodes: 3 e(1)=0 d(1)=4 Active nodes: e(3)=1 d(3)=1 e(3)=0 d(3)=1 3 3 1 4

4 2 1 1 2 4 1 2 e(2)=0 d(2)=2 e(4)=5 d(4)=0 e(1)=0 d(1)=4 4 2 1 1 2 5 4 e(4)=6 d(4)=0 1 2 e(2)=0 d(2)=2 28 Preflow-Push: Example 2 10 2

1 10 5 4 8 6 8 8 3 5 5 29 Checking if feasible flow exists Let G = (V,E) be a network with supplies and demands at each vertex b(j) > 0 indicates supply at vertex j b(j)<0 indicates demand at vertex j Assumption: xb(j) = 0 Does a flow, x, exist? Transform into a maximum flow network, G Add a source vertex, s, and a sink vertex, t. Add edge (s, j) with capacity, rsj=b(j), if b(j)>0 Add edge (j, t) with capacity, rjt=b(j), if b(j)<0 Solve max flow from s to t Result: If the max flow in G saturates all the source and sink edges,

then the original problem has a feasible solution. Otherwise, infeasible. 30 Example 1-Feasible Flow? b(2) = 5 2 b(1) = 4 1 6 2 4 4 4 b(4) = -7 8 3 b(3) = -2 31 Example 2-Feasible flow? b(2) = 5 2 b(1) = 4 1 6 3 1 4 4 b(4) = -7 8 3 b(3) = -2 32

Recently Viewed Presentations

  • LOGO Image Compression: Mathematical Means The Importance of

    LOGO Image Compression: Mathematical Means The Importance of

    Within each broad compression mechanism, we looked at images from five different categories - Venus, Earth, Mars, Jupiter, and Saturn (all images were taken from the NASA website). We compressed each photo in each category in three different ways: by...
  • Engineering Ethics: The Basics Arthur E. Schwartz, CAE

    Engineering Ethics: The Basics Arthur E. Schwartz, CAE

    -Noted ethicist Michael Josephson who established a national ethics institute several years ago identified these as the ten basic ethical values that shape inform conduct.-Obviously they have no meaning apart from context. It is like saying "Do the right thing,...
  • BSBOHS 509A:Ensure A Safe Workplace

    BSBOHS 509A:Ensure A Safe Workplace

    BSBOHS 509A:Ensure A Safe Workplace. Occupational health, safety, and security programs make significant contributions to the achievement of corporate goals by reducing costs related to absenteeism and workers' compensation, building good will in the community, protecting assets, and improving productivity
  • An Introduction to Informal Writing: Informal vs. Formal

    An Introduction to Informal Writing: Informal vs. Formal

    An Introduction to Informal Writing:Informal vs. Formal ... An informal essay shares the personality of the writer. A . formal essay. is written with a direct purpose (to persuade, to inform, to compare etc.) and follows a very strict format....
  • Twelve Channel Optical Fiber Connector Assembly: from ...

    Twelve Channel Optical Fiber Connector Assembly: from ...

    Times New Roman Arial Symbol Fireball PhotoWise Picture Microsoft Excel Chart Microsoft Excel Worksheet PowerPoint Presentation PowerPoint Presentation Objectives Performance Testing and Requirements for Optical Cable Assemblies Technology Validation Failure Modes and Testing Characterization Plan Materials Characterization Epoxy Studies MTP...
  • Anger Management

    Anger Management

    ANGER MANAGEMENT * * The key to anger reduction is knowing yourself. Do important jobs now before they become urgent. When you make mistakes, learn from them rather than getting angry.
  • Data Protection for small healthcare organisations Robert Parker

    Data Protection for small healthcare organisations Robert Parker

    Under GDPR sensitive personal data is known as special categories of data - these categories are broadly the same, but there are some minor changes. For example the special categories specifically include genetic data and biometric data where they areprocessed...
  • Looking Forward 2015: Florida State Report Conducted by

    Looking Forward 2015: Florida State Report Conducted by

    Changing market access regulations, permits, finance rules or taxation laws None of these 0.16 0.1 7.0000000000000007E-2 0.09 0.28999999999999998 0.44 Florida Members/Clients' members increasing their global or international activity Members/Clients' members adversely impacted by competition from other countries