Minimum Cost Flows - Basic Algorithms

Introduction to Minimum Cost Flows 1 The Minimum Cost Flow Problem uij = capacity of arc (i,j). cij = unit cost of shipping flow from node i to node j on (i,j). xij = amount shipped on arc (i,j) ∑(i,j)∈A cijxij Minimize ∑j xij - ∑k xki = bi for all i ∈ N. and 0 ≤ xij ≤ uij for all (i,j) ∈ A. 2 Find the shortest path from node 1 to node 6 0 2 0 4 4 2 2 1 b(1) = 1 1 2 3 4 6 b(6) = -1 2 3 0 3 5 0 The optimal flow is to send one unit of flow along 1-2-5-6. This transformation works so long as there are no negative cost cycles in G. (What if there are negative cost cycles?) 3 Find the Maximum Flow from s to t 1 10, 8 1,1 s 6, 5 2 b(i) = 0 for all i; 8,7 t 10,6 add arc (t,s) with a cost of -1 and large capacity. The cost of every other arc is 0. 13 The optimal solution in the corresponding minimum cost flow problem will send as much flow in (t,s) as possible. 4 Transshipment Problems Plants with given production capabilities for a product. One can ship directly from the plants to retailers, or from plants to warehouses, and then from warehouses to retailers. There is a given demand for each retailer. Costs of shipment are given. What is the minimum cost method for satisfying demands? 5 A Network Representation 4 Demands 190 1 6 400 7 180 310 2 Retailers 100 3 5 Plants Warehouses 6 The Caterer Problem Demand for di napkins on day i for i = 1 to 7 (so, j ∈ [1..7]). Cost of new napkins: a cents each, 2-day laundry: b cents per napkin 1-day laundry: c cents per napkin. Minimize the cost of meeting demand. 0 a clean demand arcs dirty 2 1 c 1’ 3 4 5 6 7 3’ 4’ 5’ 6’ 7’ b 2’ 7 Purchase arcs In any period of the seven periods, one can purchase napkins, at a cost of a cents per napkin. clean napkins 0 a 1 2 3 4 5 6 7 8 Demand Arcs You must use di napkins on day i dirty napkins 0 a lower bound on flows 2 1 d1 1’ 4 3 d2 2’ d3 3’ 5 d4 4’ 6 d5 5’ 7 d6 6’ d7 7’ 9 The rest of the arcs You may launder napkins in 2 days at b cents each You may launder napkins in 1 day at c cents each You may store clean napkins for free You may store dirty napkins for free Application to airplane maintenance. 0 a 2 1 c 1’ 3 4 5 6 7 3’ 4’ 5’ 6’ 7’ b 2’ 10 Some Assumptions 1. All data is integral. (Needed for some proofs, and some running time analysis). 2. The network is directed. 3. ∑i=1 to n b(i) = 0. (Otherwise, there cannot be a feasible solution) 4. There is a feasible solution (see next slide) 11 Artificial Solutions To create a feasible solution, add a dummy node d. Add an arc from d to each demand node, each with a large cost M, and large capacity. 3 2 -4 4 3 5 2 -5 1 1 3 6 d Add an arc to d from each supply node, each with a large cost M, and a large capacity. In an optimal solution, arcs with large cost will have a flow of 0. 12 Overview of the solution procedure Reduced costs ‹ recall replacing cij – πi + πj for the shortest path problem. The same transformation is very useful for min cost flow algorithms. Optimality conditions ‹ Most iterative optimization algorithms stop when “optimality conditions are satisfied”. We describe optimality conditions for the min cost flow problem. Residual network ‹ Just as in max flows, we run most algorithms on the residual network. 13 Reduced Costs Let πi denote the node potential (or dual price) for node i. cijπ = cij − π i + π j For unit of flow out of node i, subtract πi from the cost For unit of flow into node j, add πj to the cost. $3 1 2 $1 -$5 3 1 $3 – π1 + π2 2 $1 – π2 + π3 -$5 – π3 + π1 3 14 More on Using Reduced Costs Claim: For any feasible solution x, cx - cπx = πb. Thus a feasible flow x that minimizes cx will also minimize cπx. Proof: cx − cπ x = ∑ ( i , j )∈A (π i − π j ) xij = ∑ i π i ( ∑ j xij − ∑ j x ji ) = ∑ i π i bi = π b 15 Optimality Conditions Let x be a flow and let π be a vector of node potentials. The pair (x, π) is optimal if it satisfies the following: 1. x is a feasible flow cπ ij > 0, then xij = 0 2. If 3. If cπij < 0, then xij = uij 1 3 $3 -$5 2 4 If x, π satisfy (1) – (3), we say that x is an optimal flow, and π is an optimal set of node potentials. 16 The Residual Network G(x) i uij cij j 1 8 2 $10 Suppose x12 = 3 5 $10 uij - xij cij i j xij cij 1 2 3 -$10 17 Optimality Conditions for G(x) Every arc in the residual network has a nonnegative reduced cost. If cπij > 0, then xij = 0 1 8 2 If cπij < 0, then xij = uij 3 $7 Then x34 = 5 0 -$6 8 $7 2 0 -$7 4 -$6 Then x12 = 0 1 5 3 4 5 $6 18 Other optimality conditions for G(x) A feasible flow x is optimal for the minimum cost flow problem if and only if there is no negative cost cycle in the residual network G(x). 19 Negative Cycle Algorithm Algorithm NEGATIVE CYCLE; begin establish a feasible flow x in the network; while G(x) contains a negative cost cycle do begin use some algorithm to identify a negative cost cycle C; let δ : = min { rij : (i, j) ∈ C }; augment δ units of flow in cycle C and update G(x); end; end; Negative Cycle Algorithm 20 More on the Negative Cycle Algorithm Suppose that all supplies/demands are integral, and capacities are integral. Then the negative cycle algorithm maintains an integral solution at each iteration. 21 Finiteness Theorem. The Negative Cycle Algorithm is finite if all data are finite and integral. Proof. By flow decomposition, we can express the min cost flow as the sum of n+m paths and cycles. Each path and cycle has a cost bounded by nC, where C = max (|cij| : (i,j) ∈ A). The cost of the flow is at most (nC)(n+m)U, where U is the largest capacity. At each iteration of cycle canceling, the cost improves by at least one. 22 Optimality Theorem. The Negative Cycle Algorithm terminates with an optimal flow. Proof. Consider the final residual network G(x*). There is no negative cost cycle. Let d(j) denote the shortest path from node 1 to node j for each j. Let π*j = -d(j) for each j. Suppose that (i,j) ∈ G(x*). Then d(j) ≤ d(i) + cij. Therefore, cij - π*i + π*j ≥ 0, and thus cπ*ij ≥ 0. 23 Review of Cycle Canceling Given a flow x, we look for negative cost cycles in G(x). z If we find a negative cost cycle, we sent flow around the cycle z If we don’t find a negative cost cycle, we establish optimality. It is a very generic algorithm for solving minimum cost flows. Key subroutine: finding a negative cost cycle. It can be done in different ways. 24 How to Find a Negative Cycle POSSIBILITY 1. Use a shortest path algorithm to determine a negative cost cycle. POSSIBILITY 2. Find the most negative cost cycle. POSSIBILITY 3. Augment along the cycle that minimizes COST(C)/|C|. (The cost divided by the number of arcs.) POSSIBILITY 4. Simplex method. 25 Summary Some applications of the minimum cost flow problem Optimality Conditions Cycle Canceling Algorithm Integrality Property for Minimum Cost Flows 26 Opt. Conditions When Capacities Are Infinite Suppose uij = ∞ for all (i,j). Node potential vector π of node potentials π is feasible if for every arc (i,j) ∈ A, cπij ≥ 0. Lemma. If x is a feasible flow, and if π is a feasible vector of node potentials, then cx ≥ πb. Proof. We have shown that cx - cπx = πb. Therefore, cx - πb = cπx. By assumption, cπ ≥ 0 and x ≥ 0, so the result is true. 27 Strong Duality When Capacities are Infinite Strong Duality Theorem. Suppose there is a feasible flow and a feasible vector of node potentials for the uncapacitated minimum cost flow problem. Let x* be a minimum cost flow , and let π* be a maximum cost feasible vector of node potentials. (That is, it maximizes πb.) Then cx* = π*b. 28 Proof. We already know that cx* ≥ πb for any feasible vector π of node potentials. Let π’ be the vector of node potentials satisfying the optimality conditions. We claim that cx* = π’b. First, cx* - π’b = cπ’x. Next cπ’ ≥ 0 and x ≥ 0. If cπij > 0, then xij = 0 1 $3 2 Therefore, cπ’x = 0. 29