Network Optimization Generalized Flows

Generalized Flows 1 Overview of Generalized Flows Suppose one unit of flow is sent in (i,j). We relax the assumption that one unit arrives at node j. If 1 unit is sent from i, µij units arrive at j. µij is called the multiplier of (i,j) i µij = 7 j We will present: ‹LP Formulation ‹Two applications ‹Generalized Network Simplex Algorithm 2 LP Formulation of Generalized Flows xij = amount of flow sent in (i,j) µij = multiplier of (i,j) b(i) = supply at node i cij = unit cost of flow in (i,j) uij = upper bound on flow in (i,j) Minimize ∑ ( i , j )∈ A ij subject to ∑ j:( i , j )∈ A c xij xij − ∑ j:( i , j )∈A µ ji x ji = b( i ) 0 ≤ xij ≤ uij for all ( i , j ) ∈ A. 3 Conversions of physical entities i µij = 1.05 4/1/03 i coal j (i,j) represents a 1 year investment in a CD. 4/1/04 µij = .4 j electricity (i,j) represents a conversion of coal into electricity 4 Machine Scheduling i job µij = 3 j machine It takes 3 hours to make one unit of job i on machine j. xij = proportion of product i made on machine j µij = number of hours to make product i on machine j d(i) = number of units of product i that need to be made. The total time available on machine j is uj 5 Flows Along Directed Paths Suppose that 1 unit is sent from node 1, that flow is conserved in 2, 3, and 4, arrives at node 5. 1 1 µ12 = 3 2 3 µ23 = .5 3 µ34 = 4 1.5 4 6 µ45 = 1 5 6 For a directed path P from i to j, if one unit of flow is sent from i, then the amount arriving at j is: µ ( P ) = ∏ ( i , j )∈P µ ij 6 Flows Along Non-directed Paths Suppose that 1 unit is sent from node 1, that flow is conserved in 2, 3, and 4, arrives at node 5. 1 1 µ12 = 4 1 2 4 µ23 = 2 -2 3 µ34 = 6 2 2 4 µ45 = 4 -3 12 5 3 Let P be a path from i to j. P = Forward arcs of P P = Backward arcs of P If one unit of flow is sent from i, then the amount arriving at j is: µ ( P ) = ∏ ( i , j )∈P µ ij / ∏ ( i , j )∈P µ ij 7 Flows Along Cycles Suppose 1 unit is sent around W starting and ending at node 1. 2 4 1 4 1 2 -2 1 3 W 1.5 -1.5 3 2 6 4 12 2 5 4 -3 2 µ (W ) = ∏ ( i , j )∈W µ ij / ∏ ( i , j )∈W µ ij µ(W) = 1.5 If µ(W) ≠ 1, then the amount of flow arriving at node 1 is different then the amount leaving node 1. If µ(W) = 1, W is called a breakeven cycle. 8 Flows Along Cycles Suppose θ units are send around W starting and ending at node s. 2 4 1 4 2 s 3 2 W 1.5 6 2 3 5 4 4 12 The net amount arriving at node 1 is: θ[ µ(W)- 1 ]. To create a “supply” of α at node s, send α/[ µ(W)- 1 ] units of flow. 9 On the LP for Generalized Flows Minimize ∑ ( i , j )∈ A ij subject to ∑ j:( i , j )∈ A c xij xij − ∑ j:( i , j )∈A µ ji x ji = b( i ) 0 ≤ xij ≤ uij for all ( i , j ) ∈ A. The equality constraints have full row rank, which is n. A basis consists of n columns that are linearly independent. Equivalently, a basis has n columns such that no subset of these columns is dependent. 10 Augmented Trees r W An augmented tree is a connected subset of k nodes and k arcs for some k. It is a spanning tree plus an extra arc. It usually has a root. T is called good if the cycle is non-breakeven. 11 Augmented Forests 1 4 12 5 7 W1 10 9 11 6 2 W2 3 8 An augmented forest is a collection of node disjoint augmented trees including all nodes. The augmented forest is good if each cycle is non-breakeven 12 Augmented Forest Structure 1 4 12 5 7 W1 10 9 11 6 2 W2 3 8 (F, L, U) is an augmented forest structure • F are the arcs in the augmented forest. • L are the arcs at their lower bound: xij = 0 for (i,j)∈ L • U are the arcs at their upper bound: xij = uij for (i,j)∈ U 13 Node Potentials and Reduced Costs Let π(i) be the node potential for node i. π c The reduced cost of arc (i,j) is: ij = cij − π ( i ) + µ ijπ ( j ) i µij j 14 Theorem 15.5. Generalized Flow Optimality Conditions. A flow x* is an optimal solution of the generalized network flow problem if it is feasible and for some vector π of node potentials, the pair (x*, π) satisfies the following optimality conditions: (a) If 0 < xij* < uij , then cijπ = 0 (b) If xij* = 0, then cijπ ≥ 0 (c) If xij* = uij , then cijπ ≤ 0 Proof. Minimizing cx is equivalent to minimizing cπx. Exercise 15.12 15 (a) If 0 < xij* < uij , then cijπ = 0 (b) If xij* = 0, then cijπ ≥ 0 (c) If xij* = uij , then cijπ ≤ 0 Under these conditions, x* optimizes the LP Minimize ∑ ( i , j )∈A cijπ xij subject to 0 ≤ xij ≤ uij 16 Property 15.6. Augmented Forest Structure Optimality Conditions A feasible augmented forest structure (F, L, U) with the associated flow x* is an optimal augmented forest structure if for some vector π of node potentials, the pair (x*, π) satisfies the following optimality conditions. (a) For all ( i , j ) ∈ F , cijπ = 0 (b) For all ( i , j ) ∈ L, cijπ ≥ 0 (c) For all ( i , j ) ∈ U , cijπ ≤ 0 17 Computing Node Potentials for an Augmented Forest Structure 1 Compute node potentials 1. Set the potential of the root node to θ. We will determine θ later. 2. Determine the node potentials of all other nodes so that tree arcs have a reduced cost of 0. 3. Determine θ so that the extra arc also has a reduced cost of 0. $3,2 7 $1,4 $0,2 $2, 4 10 8 4 $1,3 $1,1 12 18 Computing Node Potentials θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c17 = c17 − π (1) + µ17π (7) = 0 3 - θ + 2 π(7) = 0 π(7) = (θ - 3)/2 (θ-3)/2 7 $1,4 $0,2 $2, 4 10 8 4 $1,3 $1,1 12 19 Computing Node Potentials θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c7,10 = c7,10 − π (7) + µ 7,10π (10) = 0 0 - (θ - 3)/2 + 2 π(10) = 0 π(10) = (θ - 3)/4 (θ-3)/2 7 $1,4 $0,2 $2, 4 (θ-3)/4 10 8 4 $1,3 $1,1 12 20 Computing Node Potentials θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c8,7 = c8,7 − π (8) + µ 8,7π (7) = 0 1 - π(8) + 4(θ - 3)/2 = 0 π(8) = 2θ - 5 (θ-3)/2 7 $1,4 $0,2 $2, 4 (θ-3)/4 10 8 2θ-5 4 $1,3 $1,1 12 21 Computing Node Potentials θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c7,4 = c7,4 − π (7) + µ 7,4π (4) = 0 2 - (θ - 3)/2 + 4 π(4) = 0 π(4) = (θ - 7)/8 (θ-3)/2 7 $1,4 $0,2 $2, 4 (θ-3)/4 10 8 2θ-5 4 $1,3 (θ-7)/8 $1,1 12 22 Computing Node Potentials θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c4,12 = c4,12 − π (4) + µ 4,12π (12) = 0 1 - (θ - 7)/8 + π(12) = 0 π(12) = (θ - 15)/8 (θ-3)/2 7 $1,4 $0,2 $2, 4 (θ-3)/4 10 8 2θ-5 4 $1,3 (θ-7)/8 $1,1 (θ-15)/8 12 23 NEXT: Look at the extra arc and compute θ θ 1 cijπ = cij − π ( i ) + µ ijπ ( j ) = 0 $3,2 π c4,10 = c4,10 − π (4) + µ 4,10π (10) = 0 1 - (θ - 7)/8 + 3(θ - 3)/4 = 0 8 - θ + 7 + 6θ - 18 = 0 θ = 3/5 (θ-3)/2 7 $1,4 $0,2 $2, 4 (θ-3)/4 10 8 2θ-5 4 $1,3 (θ-7)/8 $1,1 This equation has a feasible solution whenever the cycle is not breakeven. See exercise 15.20. (θ-15)/8 12 24 The Node Potentials 3/5 1 To compute the node potentials for a basis structure (F, L, U), compute the node potentials for each connected component of F. $3,2 -6/5 7 $1,4 $0,2 $2, 4 -3/5 10 4 $1,3 -4/5 8 -19/5 $1,1 -9/5 12 25 The reduced costs 3/5 1 Compute reduced costs in the usual way. $3,7 $3,2 -6/5 7 $1,4 $0,2 $2, 4 π cij = cij − π ( i ) + µ ijπ ( j ) π c10,1 = c10,1 − π (10) + µ10,1π (1) π c10,1 = 3 + 3 / 5 + 7(3 / 5) = 39 / 5 -3/5 10 4 $1,3 -4/5 8 -19/5 $1,1 -9/5 12 26 The Arc Flows 1 1 The node numbers are supplies/demands. The arc numbers are the multipliers. To compute the arc flows, set the flow in the extra arc to θ and then compute the tree arcs in the usual way as a function of θ. 2 0 7 4 2 -11 10 4 3 4 -6 1 8 1 -1 12 27 The supply of node 12 is -1 Set the flow in the extra arc to θ. 1 1 Compute the flow in (4,12) 0 7 x4,12 = 1 2 4 2 -11 10 4 3, θ 4 -6 1, 1 8 1 -1 12 28 The supply of node 8 is 1 1 1 Compute the flow in (8,7) 2 x8,7 = 1 0 7 4,1 2 -11 10 4 3, θ 4 -6 1, 1 8 1 -1 12 29 The supply of node 10 is -11 1 1 Compute the flow in (7,10) 2 (11 - 3θ)/2 2 x7,10 + 3 x4,10 = 11 x7,10 = (11 - 3θ)/2 0 7 4,1 2 -11 10 4 3, θ 4 -6 1, 1 8 1 -1 12 30 The supply of node 1 is 1 1 1 Compute the flow in (1,7) x1,7 = 1 2 1 2, (11 - 3θ)/2 0 7 4,1 2 -11 10 4 3, θ 4 -6 1, 1 8 1 -1 12 31 The supply of node 4 is -6 1 1 Compute the flow in (7,4) - 4x7,4 + x4,12 + x4,10 = -6 2 1 2, (11 - 3θ)/2 x7,4 = (6 + 1 + θ )/4 = (7 + θ )/4 0 7 4,1 2 -11 10 4 3, θ 4 8 1 -6 1, 1 1 (7 + θ)/4 -1 12 32 The supply of node 7 determines θ 1 1 x7,10 + x7,4 - 4x8,7 – 2 x1,7 = 0 2 1 2, (11 - 3θ)/2 0 7 4,1 2 -11 10 (11 - 3θ)/2 + (7 + θ)/4 – 4 – 2 = 0 (22 - 6θ) + (7 + θ) – 24 = 0 4 3, θ 4 8 1 -6 1, 1 1 (7 + θ)/4 -1 12 θ=1 33 The basic flows θ=1 1 1 2 1 2, 4 But how do we know that there will be a solution for θ? We next present an alternative approach that shows that there is a solution to the system of equations. 0 7 4,1 2 -11 10 4 3, 1 4 8 1 -6 1 1 2 1, -1 12 34 An alternative approach 1 1 Choose a node of the cycle. Say node 7. 2 0 7 Satisfy supply/demand constraints using tree arcs but ignoring node 7. Satisfy flow in node 7 by sending flow around the cycle. 2 -11 10 4 4 4 -6 1 8 1 -1 12 35 An alternative approach 1 1 x4,12 = 1 2 2, 1 x8,7 = 1 0 7 2 2, 5.5 x7,10 = 5.5 -11 10 x1,7 = 1 4 4, 1 4 4 -6 1 1, 1 8 1 -1 12 36 An alternative approach 1 1 x4,12 – 4 x7,4 = - 6 2 1 2, 1 – 4 x7,4 = - 6 0 7 2 5.5 2, x7,4 = 1.75 -11 10 Now send flow around the cycle 7-4-10-7 to cancel the excess flow at node 7. 3 4 1 4, 4 4 -6 1 1, 1 8 1 -1 12 Since the cycle is not breakeven, this is possible. Thus there is a feasible solution to this set of equations. 37 Sending flow around the cycle Send one unit out of 7 and satisfy conservation of flow at nodes 4 and 10. 6 1 2 The net result is to cancel 5 units of flow at node 7. Currently, there are 1.25 more units leaving node 7 than arriving. So, we need to send another 1.25 units to node 7. Send ¼ unit around the cycle. 7 10 12 4 4 3 4 38 What happens if U ≠ ∅ ? In computing flows, we assumed that all non-basic flows are 0. If U ≠ ∅, then we first compute the flows of arcs in U, and adjust the supplies and demands (or excess and deficits) accordingly, and then compute flows in arcs in F. 39 The generalized simplex algorithm 1. Find an initial feasible augmented forest structure (F, L, U). (This is often an artificial solution). 2. Simplex entering arc rule: find a variable that violates its optimality conditions: 1. (i,j) ∈ L with negative reduced cost 2. (i,j) ∈ U with positive reduced cost 3. Simplex leaving arc rule. Send flow in the entering arc until one of the basic arcs hits its upper or lower bound. 40 Finding the leaving arc Suppose (i,j) enters the basis. Let y be the flow obtained in F + (i,j) by setting yij = 1, and determining flows in F so that there is conservation of flow everywhere. Let x* be the basic feasible flow for (F, L, U). Choose λ maximal so that x* + λy satisfies upper and lower bound constraints. Pivot out an arc (r, s) that has hit its upper or lower bound for this choice of λ. Time to determine leaving arc is O(n). 41 A quick illustration of choosing λ Suppose x* = (2, 1, 3, 1, 0, 0, 5) Suppose y = (1, 2, -1, 0, 1, 0, 0) Suppose u = (4, 4, 4, 3, 6, 2, 5) 0 0 0 0 0 0 0 ≤ 2 1 3 1 0 0 5 + λ 1 2 -1 0 1 0 0 ≤ 4 4 4 3 6 2 5 λ≤2 λ ≤ 1.5 λ≤3 λ≤6 So, we pick λ = 1.5. And variable 2 drops out of the basis. 42 Summary The bases for generalized flow problems are good augmenting forests assuming that the graph is z connected and z has a non-breakeven cycle z The simplex algorithm can be implemented very efficiently „ O(n) time to compute the basic solution, the node potentials, and determine the leaving arc „ O(1) time to determine the reduced cost of an arc 43 A Minimal Dependent Set 2 4 1 4 2 1 3 W 1 6 3 3 5 4 4 12 2 If Ax = 0 has a nontrivial solution, then A is dependent. A breakeven cycle is a minimal dependent set. No subset is dependent. 44 Another Minimal Dependent Set A bicycle is a connected set with k nodes and k+1 arcs, with no breakeven cycle. i j C W Case 1. The two cycles are node disjoint and , and connected by a path from i to j. (possibly i = j). Send from around W starting at i, and then to j. Then cancel the flow by sending it around C. 45 Another Minimal Dependent Set A bicycle is a connected set with k nodes and k+1 arcs, with no breakeven cycle. i W C Case 2. The two cycles are node disjoint and , and connected by a path from i to j. (possibly i = j). Send from around W starting at i. Then cancel the flow by sending it around C. 46