### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Network Flows IOE 612

UM

GPA 3.76

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Industrial Engineering

This 43 page Class Notes was uploaded by Loy King on Thursday October 29, 2015. The Class Notes belongs to IOE 612 at University of Michigan taught by Katta Murty in Fall. Since its upload, it has received 24 views. For similar materials see /class/231586/ioe-612-university-of-michigan in Industrial Engineering at University of Michigan.

## Reviews for Network Flows

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

31 Single Commodity Maximum Flow Problem Katta G Murty lOE 612 Lecture slides 3 Simple Transformations 1 To get a model with a single source If many souce nodes with speci ed availabilities can introduce Supersource And convert problem into one with a single source Original model Source Availability 1 a1 units 2 lg 7 ar 2 To get a model with a single sink If many sink nodes with speci ed requirements can introduce Supersink and convert problem into one with a single sink Original model Sink Requirement 1 at least 1 units 2 exactly 2 r mar Another way to handle requirement of at least 1 at a node 1 is to make lower bound and capacity on arc 1 t equal to 0 1 respectively and look for a ow that saturates this arc 3 Transforming node capacities into arc capacities lf node i has transit capacity of 0239 split node i into a pair of ad jacent nodes onei1 say that acts as receiving end of node i handling incoming flow the other i2 say that acts as ship ping end of node i handling outgoing flow as below 4 Combining parallel arcs into one Some results Given G N AM k 5t with n IAI m problem is to nd f v to max 11 v ifz395 sto fiN fNi O ifz39y sort vifz39t ES f Ski DEFINITION Net ow in f across a cut XX Let f be a feasible ow vector in G and X X a cut separating 5 and t Then the net ow in f across this cut is de ned to be fltX7Xgt fX7Xgt Results 1 For any feasible flow vector of value v the net flow across any cut separating 5 and t is v 2 Flow value of any feasible flow vector is 3 capacity of any cut separating 5 and t So maximum ow value 3 minimum cut capacity 3 lf f is a feasible flow of value 13 and K Y is a cut separating 5 and t and 13 kK l7 El7 Y capacity of cut K 7 then f a maximum flow vector and K Y a minimum capacity cut 4 A feasible flow vector in G is of maximum value iff there exists no FAP from 5 to t WRT it Tree groth routine to nd X set of all nodes 2 with an FAP from s to 2 WRT f Step 1 Plant a tree often called the Label tree with root node at 5 ie label 5 with Q General tree growth step Look for nodes 27 satisfying Either 27 E A 139 labeled j unlabeled and f2 lt kw or ii j 39 E A j unlabeled 139 labeled and L gt 7 lf such a pair 27 is found label j with 139 Jr in case or i in case Then go to the next tree growth step lf such a pair 239 j donlt exist terminate X is the set of labeled nodes at this stage For each i E X the PAP is the predecessor path of i in the tree written in reverse order lf sink is in the label tree ie t E X event called Break through then there is an FAP from 5 to t WRT lf label tree stops growing Without sink getting labeled ie t Z X this event called Nonbreakthrough there is no FAP from 5 to t WRT f then f is a maximum ow 5 The max ow min cut theorem If a feasible ow vector exists in G Maximum ow value minimum cut capacity Duality Interpretation For simplicity assume E 0 Dual of max ow problem is min 27r u Zkz39juz39j s to 7Tj 7T U j Z O Vij A 7r5 7rt 1 7g 0 2739 Z 0 VltMgt A 7Q 077 comes from eliminating the redundant ow conserva tion eq of node t Theorem Every extreme pt of the dual system corresponds to a cut separating 5 and t through the following lf full is an extreme pt then all frumj are 0 1 and if X 7T OX z 1thenXXisaout separating 5 and t and 1 11 m E can Uz39j 0 otherwise 94 and vice versa 50 the mm cut problem ls exactly the problem of hdlhg an extreme pomt optlmum of the dual The difference between the Max cut and min cut Problems Assume k gt O The problem of nding a maximum capac ity cut is not equivalent to the LP Max 2 hzrjuzj s to constraints in the dual because the maximum objective value in this LP is 00 The max capaclty cut problem same as problem of hdmg a max ualue extreme pomt sol m thls unbounded LP an NP hard problem 1 Single path Labeling methods for max ow To nd max ow in G N AM k 5t Phase I Finds a feasible ow rst If E O f 0 will do Algorithms for Phase l when E y O are based on applying Phase ll on a modi ed network Phase II Find a max ow beginning with an initial feasible ow f0 We discuss algorithms for Phase ll rst 11 Initial Version Needs an initial feasible flow vector Tree growth occurs one branch at a time Step 1 Rooted tree planting Let f be the current feasible flow vector of value 23 Label 5 with Q Step 2 Tree growth Look for nodes 2 j satisfying one of following i Forward labeling rule 2 labeled j unlabeled 2j E A and j lt kiz39j i Reverse labeling rule 2 labeled j unlabeled j E A and f 39 gt 57239 If such pair found label j with 2 gt 2 under rule ii lfj t there is a breakthrough go to Step 3 Otherwise repeat Step 2 If no such pair nonbreakthrough go to Step 4 Step 3 Flow augmentation Let 73 be predecessor path of t written in reverse order beginning with 5 an FAP Let 6 be residual capacity of 73 and new feasible ow vector j y Where 7 6 if Lj forward 73 fzj y 6 if Lj reverse on 73 y if Lj not on 73 Chop down present tree ie erase labels on all nodes and go back to Step 1 Step 4 Termination Present ow vector is a maximum ow terminate X set of labeled nodes X complement of X then X X is a min cut Analysis when bounds irrational F amp F constructed ex ample to show algo may not work Let Or 1 VEVQ Not all arcs shown Other arcs are 25317 yuyj yumj W y j All lower bounds 0 All capacities 6 other than 4 shown in g lnitial feasible ow f0 of value 1 shown in g F amp F constructed a sequence of feasible ows frz 7 O 1 s th f 1 obtained by augmenting f V7quot and values 11 T 5 while maximum ow value is 45 100 Analysis When bounds f0 integral Each augmentation step increases ow value by gt 1 So algo nds max ow either nitely or thiro7 an in nite sequence Let u maximum arc capacity Then capacity of cut 5 N is g nu so max ow value 3 nu So no more than nu augmen tations Work between consecutive augmentations is at most So overall complexity is 0nmu a pseudopolynomial time algorithm 101 12 Scanning version Each labeled node is scanned to label all unlabeled nodes that can be labeled from it List set of labeled and unscanned nodes Step 1 Rooted tree planting Let f be the current feasible ow vector of value 13 Label 5 With Q List Step 21 Selecting a node from List to scan lf List Q go to Step 4 Otherwise delete a node i from list to scan Step 22 Scanning node i i Forward labeling Label allj unlabeled s th Lj E A and 7 lt kw With i gt and put all such j in List i Reverse labeling rule Label all j unlabeled s th j E A and f gt 57 With i and put all such j in List lf t now labeled go to Step 3 Otherwise go to Step 21 Steps 3 4 Same as in initial version 102 Sometimes better than initial version but worst case behavior same as that of initial version 103 13 Shortest Augmenting Path method Main idea At each stage select FAP to be a shortest in terms of no of arcs Algorithm Only change needed from scanning version is to maintain List as a Q ie select nodes from List to scan using FIFO discipline Theorem For all data beginning with any feasible ow vec tor this method solves max ow problem after 3 mn 2 augmen tation steps with an overall complexity of 0017712 Strongly polynomial algo 104 2 Multipath Labeling methods for Phase II ln each step these methods augment along all shortest paths simultaneously Each FAP converted into a chain by reversing orientation of reverse arcs All these chains put together yield an acyclic network called an Auxiliary network WRT present ow f ANltfgt NU AU a partial subnetvvork of residual network Cf All lower bounds in ANltfgt are 0 and upper bounds are resid ual capacities Also Af U A f Where Lj E Af gt Lj E Af j lt kw and my capacity in l Ale kw f j Lj E A f gt j 39 E Afj gt 57 and my capacity in AN sz sz These methods nd a maximal or blocking ow in ANltfgt and augment f in G using it We denote ow vectors in ANltfgt by g 92739 105 General multipath labeling method for max imum flow Step 1 Initiate the method with a feasible flow vector f0 in G Step 2 Let f be the current feasible flow vector in G Construct auxiliary network ANltf Two possible outcomes 0 Construction stops without t joining auxiliary network Then f is a maximum flow in G lf X set of all nodes in aux iliary network and X its complement X X is a min cut separating 5 and t Terminate o t joins the auxiliary network at some stage Stop construction and go to Step 3 Step 3 Find a maximal or blocking flow 9 92739 in the aux iliary network Different multipath methods use different methods for this Step 4 Augmentation Compute new vector f fz39j in 106 G by 1 if 13 9 AU fw fzj g j W133 E Altfgt fzj 92739 if hi E A7 Value of f in G Value of f in G Value of g in ANf Go back to Step 2 with f 107 Dl lC78 method The auxiliary network used is called Layered Network f Nodes N0 in it are partitioned into nonempty subsets N0 5 N1 M called Layers lf f is not a maximum ow in G the last layer will contain t Arcs in layered network always go from one layer to next De nition Length of 1 number of layers 108 Layered network construction Step 1 Initialization JVO General step to construct next layer Let M be last layer constructed For each i E M do for each j s th Lj E A and fzj lt kw put j in MH and M in At1ltfgtwith F627 kw fw for each j s th j 39 E A and f gt E put j in MH and M in AF1ltfgtWith my sz39 572 lf MH Q let X UfFOJVu and X its complement f is a maximum ow in G and X X is a min cut terminate Dinics algo o If t E MH let UfFOJVu U A f NU stop construction 0 Otherwise go to next step in construction 109 110 Dinic s Procedure for nding Maximal Block ing ow in L N A 0 H 523 Begins with go O and augments ows along FACs detected by DFS F denotes current set of eligible arcs to include in FAC Up dated by deleting saturated arcs etc Step 1 Initialization go O is current ow in L F A Step 2 Initiate DFS lnitiate DFS by labeling 5 with Q and making it current node Step 3 DFS Let i E M be current node o If F has no arc incident out of 239 go to Step 6 if i 5 or Step 5 if 2 y 5 o If F has some arcs incident out of 239 select one say 17 Label j with Pl 239 lf j t predecessor path of t in reverse order is FAC go to Step 4 111 lf j y t make j the new current node and repeat this step Step 4 Augmentation Augrnent ow using FAC delete all saturated arcs from F erase labels on all nodes and go to Step 2 Step 5 Updating F No FAC through current node 239 Let p Pl of 239 Delete all arcs incident into i from F make p next current node go back to Step 3 Step 6 Stop Present ow vector 9 is maximal terniinate 112 113 Theorem ln Dinicls method each successive layered network is strictly longer than the previous Theorem At most 71 1 layered networks need to be con structed in Dinicls method 114 22 Dinic MKM Malhotra Kumar Ma heswari method Auxiliary network used is Referent a partial subnetwork of L Procedure for nding blocking ow not based on FACs but uses new operations called Flow pushing ow pulling Backward pass routine to nd Referent R from L Layered network L may have nodes other than t in last layer NL Flows on arcs incident into them will be 0 in every blocking ow This removes such O ow arcs 0 Delete all nodes other than t from last layer NL and all arcs incident at such nodes from L 0 Delete all nodes which have no arcs incident out of them and all arcs incident into those nodes Repeat this step until no further deletions are possible Remaining part of layered network called referent lt is a union of simple chains from 5 to t 115 F denotes set of eligible arcs of R at current stage and Y denotes the set of nodes on arcs in F Let g be a feasible ow vector in R and Y F the current sets For each i E Y WRT g Y F we de ne OM Inpotential ofz39 Ej eFlt j 97239 Outpotential ofz39 Elt 7j Flt Zj 92y ifz s owpotential of 239 04139 iii t rnin0zz39 ifi 7g 5 t 116 MKM procedure for nding blocking flow in R Step 1 Initialization Start with go O in R N A O K s t F A Y N Compute Vi E NWRT go F Y All these initial Will be gt 0 Step 2 Reference node selection Reference poten tial p rninpi i E Y and p a node that attains this min p called reference node Step 31 Flow Pushing Push excess flow of p out of p increase flow on arcs of F in forward star of p l by l saturating them until total increase reaches p In this process at most one outgoing arc has flow increase but remains unsaturated This has pushed flow from p to nodes in next layer For each of those nodes push the excess flow reaching there out of that node exactly same way Repeat for nodes in next layer amp continue until all excess flow of p units reaches t Step 31 Flow Pulling Pull excess flow of p into p in 117 crease ow on arcs of F in reverse star of p 1 by 1 saturating them until total increase reaches p In this process at most one incoming are has flow increase but remains unsaturated This has pulled ow into p from nodes in previous layer For each of those nodes pull the excess ow going out of it into that node exactly same way Repeat for nodes in previous layer amp continue until all excess ow of p units is pulled out of 5 After Steps 31 32 are completed we again have a feasible ow vector Step 4 Updating FYpz39s 41 Delete all saturated arcs from F 42 lf all arcs into or all arcs out of a node q are deleted from F delete Q from Y and all arcs incident at Q from F Repeat until no further deletions are possible 43 Update in out and ow potentials of nodes in Y WRT present ow and sets Y F o If O for some i E Y go to Step 5 if pltsgt or plttgt is 0 otherwise if ps plttgt are both gt O delete all nodes i With 118 0 from Y and all arcs incident at them from F Now apply 42 after which go to 43 again o If gt O W E Y go to Step 2 Step 5 Stop Present ow vector is blocking stop prooe dure Theorem The overall complexity of Dmio MKM algorithm for maximum ow is 0013 119 120 3 Pre ow Push methods for Phase II Newer algorithms First consider lower bound vector E O A pre ow is a ow vector not necessarily feasible 9 92739 satisfying 0 0 g g g k ie bounds hold on all arcs 0W 75 st net ow into node 239 6239 gNi gz J Z O Pre ovvs rst introduced by Karzanov Active node Node 139 said to be an active node in pre ovv 9 iff 6239 gt O 121 These methods work by pushing excess from active nodes to t or to 5 if t is not reachable from them Terminate when no active nodes left ie when ow vector becomes feasible it Will be a maximum ow These methods due to Goldberg Tarzan use a node dis tance vector is an estimate of the distance in terms of arcs from node i to t in the residual network Cg N Ag O lt satis es following Validity conditions 0 Z O and integer W o dt O ds n o If Lj E Ag then d 3 dj 1 So if lt n it is a lower bound on actual distance from i to t in Cg And if Z n n is a lower bound on actual distance from 5 to i in Cg Arc 27 E Cg is said to be admissible arc WRT d if i is an active node and dltjgt 1 122 General Preflow push algorithm Initialization De ne initial 90 by 27 lfi 8 92739 0 otherwise De ne initial d0 by one of the following two choices Simplest choice is to take d0i n if i 5 0 otherwise The better choice is to take d0i to be the distance labels obtained in a backwards BrFS of C90 starting at node t General Step Let g d be present preflow distance label pair lf no active nodes 9 is a maximum feasible flow terminate lf active nodes exist perform one of following two operations Push Select an active node i and an admissible arc Lj incident out of it in Cg lf Lj has a label label in Gg increase gzj decrease g by e minei my This push operation is saturating if e my nonsaturating 123 otherwise lt decreases 6139 by 6 and increases 6 j by 6 if j y t Relabel Select an active node i with no admissible arcs inci dent out of it in Cg So j s th Lj E Altggt gt 3 dj Change to niin1 dltjgtz j s th Lj E Ag This relabel operation resets to highest value allowed by validity conds lt creates at least one adniissible arc at active node i on which a push operation can be carried out next Complexity of this algo 3 0012771 amp can be improved to 0013 by rules for selecting active nodes adniissible arcs amp order in which push relabel are applied 124 How to nd max ow by pre ow push when 0 Needs two phases Phase l next section nds a feasible ow vector by applying the max ow algorithm on a modi ed network in which all lower bounds are 0 so this can be solved by the above pre ow push algo Phase ll Let f be the feasible ow vector obtained in Phase I Apply the above pre ow push algo to nd a max ow in N AG 0 H 5 t let it be h my Then a maximum ow in G is f where j hz39j if E With label amp hz39j gt 0 fm39 j h 39 if m e Af with label amp h 39 gt 0 fzj otherwise 125 Phase I for problems with 6 y 0 Assume 0 g E g k Purpose to nd a feasible ow vector or establish infeasibility ln G compute EiNENi W E N and KN N A Feasible circulation is a ow vector satisfying bounds on all arcs in which ow conservation holds at every node ow in ow out at every node Modify G by adding an arti cial arc t 5 with ts 0163 00 and call niodi ed network G1 lf f is a feasible ow vector of value v in G f fts v is a feasible circulation in G1 amp vice versa So Phase l problem can be solved by nding a feasible circulation in G1 ln G1 since we want to nd a feasible circulation there are no source and sink and 5 t are like any other nodes Now we transform the problem of nding a feasible circulation in G1 into a max ow problem on another niodi ed network G in which all arc lower bounds are zero G is obtained from G1 126 by making following changes 0 Add arti cial source sink nodes 5 t to G1 0 W s th KAN y 0 add the arti cial arc i t with lower bound 0 capacity KAN o W s th KN y 0 add the arti cial arc 5 with lower bound 0 capacity KN o Vij E A with EM y 0 change its lower bound to O and capacity to kw EM Resulting network is G Phase I Algorithm Find maximum ow in G from 5 to t Since all arc lower bounds in G are 0 this can be found by any algo discussed earlier beginning with O ow in G Let maximum ow be f with value 11 o lf 11 lt EltNN there exists no feasible circulation in G1 and hence no feasible ow in G H11quot MAN let f j jg My m e A Then f f is a feasible circulation in G1 and f is a feasible ow vector in G of value fig 127 128 Existence conditions for a feasible Circula ti0n Theorem Given G N A E k with 0 g E g k a feasible Circulation exists in G iff kX X 2 m X VX c N X NX 129

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.