Networks 2 Maximum Flows

z The maximum flow problem 1 Goal of this lecture z Introduce the maximum flow problem z Discuss applications of flows z Present the Ford-Fulkerson max flow algorithm z Present the max-flow min-cut result 2 The Maximum Flow Problem z Directed Graph G = (N, A). – Source s – Sink t – Capacities uij on arc (i,j) – Maximize the flow out of s, subject to – Flow out of i = Flow into i, for i ≠ s or t. 10 1 8 1 s 6 2 t 10 A Network with Arc Capacities 3 An application of maximum flow z In a communication network, a computer s wants to send as much communication as possible per unit time to another computer t. 10 8 1 1 s 6 2 t 10 4 An application of maximum flow An oil company wants to ship as much oil as possible per unit time from an oil field to a refinery through pipes. How much oil can shipped? 10 10 8 8 11 s s 1 1 66 2 tt 10 10 5 Feasible flows z Flow in arc (i, j) is at most its capacity z Total flow into node 1 = total flow out of node z Total flow into node 2 = total flow out of node 2 10 1 8 1 s 6 7 2 10 1 7 0 s 6 2 6 t Network with capacities t Network with a feasible flow 6 10 1 8 1 s 6 7 2 10 1 6 1 s 6 9 2 7 1 8 1 s 6 2 7 t Network with capacities t Another feasible flow t A maximum flow 7 Representing the Max Flow as an LP 10, 9 1 1,1 s 6, 6 2 max v s.t xs1 + xs2 t 10,7 max = v -xs1 + x12 + x1t = 0 -xs2 - x12 + x2t = 0 -x1t - x2t Flow out of i - Flow into i = 0 for i ≠ s or t. 8,8 = -v 0 ≤ xij ≤ uij for all (i,j) s.t. v Σj xsj = v Σj xij – Σj xji = 0 for each i ≠ s or t s.t. - Σi xit = -v 0 ≤ xij ≤ uij for all (i,j) 8 Applications of Network Flows Applications Physical analog of nodes Physical analog of arcs Flow phone exchanges, Voice messages, Cables, fiber optic computers, Data, Communication links, microwave transmission Video systems relay links facilities, satellites transmissions Hydraulic systems Pumping stations Reservoirs, Lakes Pipelines Water, Gas, Oil, Hydraulic fluids Integrated computer circuits Gates, registers, processors Wires Electrical current Mechanical systems Joints Rods, Beams, Springs Heat, Energy Transportation systems Intersections, Airports, Rail yards Highways, Airline routes Railbeds Passengers, freight, vehicles, operators 9 Getting started in finding a maximum flow z Look for a path from s to t. z Send as much flow on the path as possible. 10 1 8 1 s 6 2 t 10 You can send min {10, 8} units of flow on the path. 1 s t 2 10 The Residual Network z Let x be a flow. Let G(x) denote how flows can change starting from flow x. 10 1 8 10, 8 1 s 6 t 6, 0 1 Two more units of flow can be sent from s to 1 8 s 6 2 t 10, 0 The first flow x The original network 2 8, 8 1, 0 s 10 2 1 8 1 2 t 10 The residual network G(x) Eight units of flow can be returned from node 1 to s. 11 More on the Residual Network 10, 8 1 8, 8 1, 0 s 6, 0 uij, xij t i j 10, 0 2 The flow x and capacities 1 2 8 s 6 8 uij - xij 1 2 t 10 i j xij The residual network G(x) 12 Augmenting paths and the residual network z An augmenting path is a path from s to t in the residual network. z The residual capacity of the augmenting path P is δ(P) = min{rij : (i,j) ∈ P}. z To augment along P is to send δ(P) units of flow along each arc of the path. We modify x and the residual capacities appropriately. 1 2 8 s 6 The residual capacity of s-2-t is 6. 8 1 2 t 10 The residual network G(x) The residual capacity of s-1-2-t is 1. 13 The Ford Fulkerson Maximum Flow Algorithm Begin x := 0; while there is some directed path from s to t in G(x) do begin let P be a path from s to t in G(x); send δ(P) units of flow along P; update x and G(x); end end {the flow x is now maximum}. 14 Ford-Fulkerson Max Flow 4 2 3 5 1 1 1 2 2 s 4 3 1 t 2 3 This is the original network, and the original residual network. 15 Ford-Fulkerson Max Flow 4 2 3 5 1 1 1 2 2 s 4 3 1 t 2 3 Find any s-t path in G(x) 16 Ford-Fulkerson Max Flow 4 2 3 5 1 1 2 1 2 s 4 2 3 1 1 2 1 t 1 3 Determine the capacity ∆ of the path. Send ∆ units of flow in the path. Update residual capacities. 17 Ford-Fulkerson Max Flow 4 2 5 3 1 1 2 1 2 s 4 2 3 1 1 2 1 t 1 3 Find any s-t path 18 Ford-Fulkerson Max Flow 4 2 5 3 1 1 2 1 s 2 3 1 11 4 1 1 1 3 2 1 1 t 1 Determine the capacity ∆ of the path. Send ∆ units of flow in the path. Update residual capacities. 19 Ford-Fulkerson Max Flow 4 2 5 3 1 1 2 1 s 2 3 1 11 4 1 1 1 3 2 1 1 t 1 Find any s-t path 20 Ford-Fulkerson Max Flow 4 2 5 3 1 1 1 s 2 3 1 11 4 1 2 1 1 3 1 1 2 t 1 Determine the capacity ∆ of the path. Send ∆ units of flow in the path. Update residual capacities. 21 Ford-Fulkerson Max Flow 4 2 5 3 1 1 1 2 s 2 3 1 11 4 1 2 1 1 3 1 1 2 t 1 Find any s-t path 22 Ford-Fulkerson Max Flow 4 2 5 3 1 1 1 1 2 s 1 2 11 4 1 2 1 2 1 3 1 1 2 t 2 1 Determine the capacity ∆ of the path. Send ∆ units of flow in the path. Update residual capacities. 23 Ford-Fulkerson Max Flow 4 2 5 3 1 1 1 2 s 1 2 1 11 4 1 2 1 2 t 1 2 1 3 2 1 Find any s-t path 24 Ford-Fulkerson Max Flow 4 3 2 1 3 2 1 5 1 1 1 s 1 2 1 4 1 2 1 2 t 1 2 1 3 2 1 Determine the capacity ∆ of the path. Send ∆ units of flow in the path. Update residual capacities. 25 Ford-Fulkerson Max Flow 4 3 2 1 3 2 1 5 1 1 1 s 1 2 1 4 1 2 1 2 t 1 2 1 3 2 1 There is no s-t path in the residual network. This flow is optimal 26 Ford-Fulkerson Max Flow 1 2 5 1 1 2 2 s 4 2 t 2 3 Here is the optimal flow 27 Comments z If a “good” augmenting path is found, the algorithm can be efficient – fewest number of arcs – augmentation with largest capacity z It can be terrible if one is permitted to choose “bad” augmenting paths z But it is finite so long as the data is all integer valued. And the optimum flows are integral so long as the data is integral. 28 A simple and very bad example 1 M s M 1 M M t 2 29 After 1 augmentation 1 M-1 M 1 s 1 M-1 M 2 t 1 30 After two augmentations 1 M-1 1 s M-1 1 1 M-1 M-1 1 2 t 1 31 After 3 augmentations 1 M-2 M-1 2 1 s 1 M-2 M-1 1 2 t 2 32 And so on 33 After 2M augmentations 1 M s M t 1 M 2 M Next topic: how do we recognize a maximum flow. 34 How do we know when a flow is maximum? 4, 1 1 4 1 1 3, 1 2, 2 s 3 3, 2 In this case, there is a flow of 5 units from s to t. 1 2 1, 1 2, 2 t 2, 2 How do we know that there is no flow from s to t that is more. 35 How do we know when a flow is maximum? 4, 3 5 8 1 1 3, 3 2, 2 4, 3 3, 2 s 6 2, 2 In this graph, there is a flow of 7 units from s to t. 1 7 t 2, 2 How do we know that there is no flow from s to t that is more? 36 How do we know when a flow is maximum? 3, 2 1, 1 1 1, 1 s 2, 2 In this graph, there is a flow of 8 units from s to t. 2 t 5, 3 How do we know that there is no flow from s to t that is more? 37 Cuts in graphs z An s-t cut is a partition of the nodes N into two parts S and T = N\S with s ∈ S, and t ∈ T. z The capacity of the cut (S, T) is the sum of the capacities of arcs directed from S to T. 3 1 1 1 s 2 2 t 5 If S = {s}, then capacity of (S, T) = 5. If S = {s, 1}, then capacity of (S, T) = . If S = {s, 1, 2}, then capacity of (S, T) = . 38 Max-Flow Min-Cut (1) z Let (S, T) be any minimum s-t cut. Then the maximum s-t flow is at most the capacity of the cut (S, T) 3 1 1 1 s 2 2 t 5 Intuition: any flow from s to t has to cross the cut. So, one cannot send more than 4 units of flow from s to t. 39 Max-Flow Min-Cut (2) Max Flow Min Cut Theorem. Ford-Fulkerson. The maximum flow from s to t is the minimum capacity of an s-t cut. 3 1 1 1 s 2 2 t 5 Given a max flow x*, there always is a cut that proves that no more flow from s to t is possible. 40 Initial Application of Flows z Military operations in Europe – General F. S. Ross developed the model – brought the model to Ford and Fulkerson at Rand – Evaluate the capacity of the Eastern European rail network to support a conventional war. 41 What is the maximum number of arcdisjoint s-t paths? 1 5 9 2 6 10 t s 3 7 11 4 8 12 There are 3 arc-disjoint s-t paths Introduce myself and the Tas. It is critical that students sign up for the virtual campus web site. Hand out instructions on how to use it. Make sure that everyone signs up on the list. Also, create a class list that is separate from the web site. Ask for a show of where students come from. There should be four major contingencies: Grad EECS, ORC, Transportation, Rest 42 What are the fewest number of arcs whose deletion eliminates all paths from s to t? 1 5 9 2 6 10 t s 3 7 11 4 8 12 Let S = {s, 3, 4, 8}. The only arcs from S to T = N\S are the 3 deleted arcs. Introduce myself and the Tas. It is critical that students sign up for the virtual campus web site. Hand out instructions on how to use it. Make sure that everyone signs up on the list. Also, create a class list that is separate from the web site. Ask for a show of where students come from. There should be four major contingencies: Grad EECS, ORC, Transportation, Rest 43 z Theorem. The maximum number of node-disjoint paths from s to t is equal to the minimum number of arcs whose deletion leaves no paths from s to t. 44 Summary and Extensions z 1. Augmenting path theorem z 2. Ford-Fulkerson Algorithm z 3. Duality Theory. z 4. Computational Speedups. 45 The feasibility problem: find a feasible flow warehouses 6 5 4 5 4 retailers 1 2 3 4 6 6 7 7 8 6 9 5 5 Is there a way of shipping from the warehouses to the retailers to satisfy demand? 46 Transformation to a max flow problem warehouses 6 6 5 5 s 4 4 5 5 4 4 retailers 1 2 3 4 6 66 7 77 t 8 66 9 55 5 There is a 1-1 correspondence with flows from s to t with 24 units (why 24?) and feasible flows for the transportation problem. 47 The feasibility problem: find a matching persons tasks 1 5 2 6 3 7 4 8 Is there a way of assigning persons to tasks so that each person is assigned a task, and each task has a person assigned to it? 48 Transformation to a maximum flow problem persons tasks 1 5 2 6 1 s 1 1 1 1 1 1 3 t 7 1 4 8 Does the maximum flow from s to t have 4 units? 49 Application 6.4 Scheduling on Uniform Parallel Machines Job(j) 1 Processing 1.5 Time 2 3 4 3 4.5 5 Release 2 0 2 4 Time Due Date 5 4 7 9 Suppose there are 2 parallel machines 2 1 4 3 No schedule is possible unless preemption is allowed 50 Application 6.4 Scheduling on Uniform Parallel Machines Job(j) 1 Processing 1.5 Time 2 3 4 3 4.5 5 Release 2 0 2 4 Time Due Date 5 4 7 9 Suppose there are 2 parallel machines 2 1 3 4 4 3 A feasible schedule with preemption allowed 51 Transformation into a maximum flow problem red arcs: the amount of processing of job j during t time units is at most t. 2 0-2 1 4 1.5 3 s 4.5 5 2-4 2 1 3 2 4-5 t 4 4 blue arcs: the amount of processing of job j over all time units is pj. 4 green arcs: the amount of processing during t time units is at most Mt. 5-7 4 2 7-9 52 A maximum flow There is a feasible schedule if there is a maximum flow that saturates each of the arcs out of s. 1.5 3 s 4.5 5 Flow decomposition can be used to transform flows into schedules 0-2 1 1 .5 2 2 1 4,2 2-4 2 3 .5 2 1 4 2 2 4-5 4,4 2,2 t 4,4 5-7 4,2 7-9 53