C&O 355 Mathematical Programming Fall 2010 Lecture 18

C&O 355 Mathematical Programming Fall 2010 Lecture 18

C&O 355 Mathematical Programming Fall 2010 Lecture 18 N. Harvey Topics Network Flow Max Flow / Min Cut Theorem Total Unimodularity Directed Graphs & Incidence Matrices Proof of Max Flow / Min Cut Theorem Network Flow

Let D=(N,A) be a directed graph. Every arc a has a capacity ca0. (Think of it as an oil pipeline) Want to send oil from node s to node t through pipelines Oil must not leak at any node, except s and t: flow in = flow out. How much oil can we send? For simplicity, assume no arc enters s and no arc leaves t. 3 5 s 4

7 8 1 1 1 t 2 2 2 1

2 3 2 Max Flow & Min Cut Harris and Ross [1955] Schematic diagram of the railway network of the Western Soviet Union and Eastern European countries, with a maximum flow of value 163,000 tons from Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as The bottleneck. [Schrijver, 2005] Max Flow & Min Cut Let D=(N,A) be a digraph, where arc a has capacity ca. Definition: For any UN, the cut +(U) is: The capacity of the cut is:

Delbert Ray Fulkerson Theorem: [Ford & Fulkerson 1956] The maximum amount of flow from s to t equals the minimum capacity of a cut +(U), where s2U and t2U Furthermore, if c is integral then there is an integral flow that achieves the maximum flow. LP Formulation of Max Flow Variables: xa = amount of flow to send on arc a Constraints: For every node except s & t, flow in = flow out. Flow through each arc can not exceed its capacity. Objective value: Total amount of flow sent by s. Notation: +(v) = arcs with tail at v -(v) = arcs with head at v The LP is:

Incidence Matrix of a Directed Graph What is the matrix M defining the constraints of this LP? Row for every node (except s or t) Column for every arc Mv,a = +1 if node v is the head of arc a -1 if node v is the tail of arc a 0 otherwise Goal: Analyze extreme points of this LP. Plan: Show M is totally unimodular. Total Unimodularity Let M be a real mxn matrix

Definition: Suppose that every square submatrix of M has determinant in {0, +1, -1}. Then M is totally unimodular (TUM). In particular, every entry of M must be in {0, +1, -1} Key point: Polytopes defined by TUM matrices have integral extreme points. For example, last time we showed: Lemma: Suppose M is TUM. Let b be any integer vector. Then every basic feasible solution of P = { x : Mxb } is integral. Total Unimodularity Let M be a real mxn matrix Definition: Suppose that every square submatrix of M has determinant in {0, +1, -1}. Then M is totally unimodular (TUM). Lemma: Suppose A is TUM. Let b be any integer vector. Then every extreme point of P = { x : Mxb } is integral. Claim: Suppose M is TUM. Then Proof: Exercise?

is also TUM. Corollary: Suppose M is TUM. Let b and c be integer vectors. Then every extreme point of P = { x : Mx=b, 0xc } is integral. Incidence Matrices are TUM Let D=(N, A) be a directed graph. Define M by: Mu,a = +1 if node u is the head of arc a -1 if node u is the tail of arc a 0 otherwise Lemma: M is TUM. Proof: Let Q be a kxk submatrix of M. Argue by induction on k. If k=1 then Q is a single entry of M, so det(Q) is either 0 or 1. So assume k>1.

Lemma: M is TUM. Proof: Let Q be a kxk submatrix of M. Assume k>1. Case 1: If some column of Q has no non-zero entries, then det(Q)=0. Case 2: Suppose jth column of Q has exactly one non-zero entry, say Qt,j 0 Use Column Expansion of determinant: , where t is the unique non-zero entry in column j. By induction, det Qdel(t,j) in {0,+1,-1} ) det Q in {0,+1,-1}. Case 3: Suppose every column of Q has exactly two non-zero entries. For each column, one non-zero is a +1 and the other is a -1. So summing all rows in Q gives the vector [0,0,,0]. Thus Q is singular, and det Q = 0.

The Max Flow LP Observations: The LP is feasible (assume the capacities are all non-negative) The LP is bounded (because the feasible region is bounded) It has an optimal solution, i.e., a maximum flow. (by FTLP) The feasible region is where M is TUM. Corollary: If c is integral, then every extreme point is integral, and so there is a maximum flow that is integral. Q: Why does P have any extreme points? A: It contains no line. Max Flow LP & Its Dual Dual variables: A variable yv for every v 2 N \ {s,t}

A variable zuv for every arc uv The dual is Lets simplify: Set ys = 1 and yt = 0 The Dual where ys and yt are not variables: ys = 1 and yt = 0 We will show: Given an optimal solution (y,z), we can construct a cut +(U) such that Rounding In other words, the capacity of the cut +(U) equals the optimal value of the dual LP. By strong LP duality, this equals the optimal value of the primal LP, which is the maximum flow value. Every cut has capacity at least the max flow value,

so this must be a minimum cut. =2 a t 1 U3 3 c U4 U5 =5 d

s 4 0 6 b 1 Let (y,z) be an optimal dual solution Every node u lies at some position yu on the real line Number the nodes 1,,n so that y1 yn Suppose node t numbered and node s numbered Let Ui = { i, i+1, , n }, for < i (Here n=|N|, the total # nodes) Pick cut Ui with probability yi - yi-1

Arc jk contributes 0 if jk So =2 a t 1 U3 3 c U4 U5 =5

d s 4 0 6 b 1 Let Ui = { i, i+1, , n }, for < i Pick cut Ui with probability yi - yi-1 By dual feasibility = Optimum value of Dual LP

So the average capacity of the Uis is Dual Opt. Value ) minimum capacity of a Ui is Dual Opt. Value, and so it is a minimum cut. Summary We have proven: Theorem: [Ford & Fulkerson 1956] The maximum amount of flow from s to t equals the minimum capacity of a cut +(U), where s2U and t2U Furthermore, if c is integral then there is an integral flow that achieves the maximum flow. We also get an algorithm for finding max flow & min cut

Solve Max Flow LP by the ellipsoid method. Get an extreme point solution. It is an integral max flow. Solve Dual LP by the ellipsoid method. Use rounding method to get a min cut. This algorithm runs in polynomial time

Recently Viewed Presentations

  • Tips for Using This Template

    Tips for Using This Template

    A new feature offered this year, is the option to print the ISRs in Spanish. There are two ways to print ISRs. One option is to drill down to an individual student's score through the "Score Reports" section of ORS...
  • 13.4 Blood Vessels

    13.4 Blood Vessels

    A microcirculation of interwoven networks of capillaries, consisting of: Vascular shunts - metarteriole-thoroughfare channel connecting an arteriole directly with a postcapillaryvenule. True capillaries - 10 to 100 per capillary bed, capillaries branch off the metarteriole and return to the thoroughfare...
  • Unit 1: Color Theory Using Color Pencil Techniques

    Unit 1: Color Theory Using Color Pencil Techniques

    Unit 1 Project. For this project, you will use all five color pencil techniques you learned in class to complete a coloring book page. You may bring in your own coloring page (from a coloring book or printed from the...
  • Disorders of Peripheral Nerves

    Disorders of Peripheral Nerves

    In partially injured nerves the uninjured fibers may increase expression of aipha -adrenoreceptors. In both , sympathetically mediated pain may occur. Sympathetic blocks or by the administration of systemic a-adrenoreceptorantagonists (phentolamine)
  • The cardiovascular system

    The cardiovascular system

    Cardiac Output (CO) amount of blood pumped out by each ventricle in 1 min. Stroke Volume (SV) = vol of blood pumped out by 1 ventricle with each beat. correleates with force of ventricular contraction. CO = HR x SV...
  • Introduction This is an in journey back in

    Introduction This is an in journey back in

    Introduction This is an in journey back in time to the 1000 in Europe where you chose your path of discovery from different time period and different mode of travel.
  • PSSA QUESTION OF THE DAY #1 Which of

    PSSA QUESTION OF THE DAY #1 Which of

    Courtney traveled to the mountains each year for a ski trip with her family. ... Reasoning: Each of the sentences calls for a third-person, plural pronoun. The correct answer is "The two sisters rarely got along as they were so...
  • What is Financial Aid? - Collin College

    What is Financial Aid? - Collin College

    Increases your knowledge of the financial aid process and provides information about other sources of aid. Another feature of FAFSA4caster is the "FAFSA4caster Tip". These tips appear throughout the site and provide you with information that will help make preparing...