Networks 3 - Minimum Cost Flows Plus More

z The Minimum Cost Flow Problem 1 Review of 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 2 A maximum flow S 3, 2 1, 1 1 1, 1 s 2, 2 2 t 5, 3 T Capacity(S, T) = 4 = value of max flow from s to t 3 The Minimum Cost Flow Problem Network G = (N, A) Node set N = {1, 2, 3, 4} A network with costs, capacities, supplies, demands 3 Arc set A = {(1,2), (1,3), (2,3), (2,4), (3,4)} Capacities uij on arc (i,j) -$3,6 4 1 $8, 5 2 $3, 4 $7, 2 $2, 7 •e.g., u12 = 6 Cost cij on arc (i,j) 3 4 -2 -5 •e.g., c12 = $3 Supply/demand bi for node i. • e.g. b1 = 4 (supply) • b3 = -5 (demand) Send flow in each arc Satisfy “supply/demand” constraints” Satisfy flow bound constraints Minimize cost 4 Minimum Cost Flows vs Max flows. 10 1 8 1 s 6 2 -$3,6 t 10 A Max Flow Problem 4 1 2 $8, 5 $7, 2 $3,4 $2, 7 -5 A Minimum Cost Flow Problem No costs on arcs z Costs on arcs z special nodes s and t z no “special nodes” z flow into j = flow out of j for j ≠ s, t z Flow out of j – flow into j = bj z Assumption: z want min cost flow want max flow from s -2 3 z z 4 Σj bj = 0 5 3 The LP Formulation -$3,6 4 1 -z x12 x13 x23 x24 x34 $8, 5 1 -3 8 7 3 2 = 0 0 0 0 0 1 -1 0 0 1 0 -1 0 0 1 -1 0 0 1 0 -1 0 0 1 -1 = = = = 4 3 -5 -2 0 ≤ x12 ≤ 6, 0 ≤ x13 ≤ 5, 0 ≤ x24 ≤ 4, 0 ≤ x34 ≤ 7, 0 ≤ x23 ≤ 2, 2 $3, 4 $7, 2 3 $2, 7 4 -2 -5 Supply/Demand constraints Lower and upper bounds on variables The constraint matrix is the node arc incidence matrix 6 The Minimum Cost Flow Problem Let xij be the flow on arc (i, j). Minimize the cost of sending flow s.t. Flow out of i - Flow into i = bi 0 ≤ xij ≤ uij Minimize ∑ n s.t. ( i , j )∈ A n ∑ x −∑ x j=1 ij k=1 ki c ij x ij = bi for all i 0 ≤ xij ≤ uij for all (i,j) 7 Theorem. If the constraint matrix for a linear program is a node-arc incidence matrix, and if the RHS is integral, then all basic feasible solutions are integral. Corollary. The optimal solution that the linear program gives you for the minimum cost flow problem is integer valued. Note: Most linear programs can have fractional solutions. x + y = 1, x – y = 0. Unique solution (.5, .5) 8 Some Information on the Min Cost Flow Problem z Reference text: Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, and Orlin z 15.082J/6.885J: Network Optimization z Polynomial time simplex algorithm (Orlin [1997]) z Basic feasible solutions of a minimum cost flow problem are integer valued (assuming that the data is integer valued) z Very efficient solution techniques in practice 9 The Transshipment Problem: Flows representing shipments z Plants with given production capabilities for a product. z One can ship directly from the plants to retailers, or from plants to warehouses, and then from warehouses to retailers. z There is a given demand for each retailer. z Costs of shipment are given. z What is the minimum cost method for satisfying demands? 10 A Network Representation 4 Demands z Ship from plants to warehouses or retailers z Ship from warehouses to retailers z Flow into warehouse – flow out of warehouse z costs on all arcs z upper bounds on arcs 190 1 6 400 7 180 310 2 Retailers 100 3 5 Plants Warehouses 11 The Caterer Problem: flows representing movements and transformations z Demand for di napkins on day i for i = 1 to 7 z Cost of new napkins: a cents each, z 1-day laundry: b cents per napkin z 2-day laundry: c cents per napkin. z Minimize the cost of meeting demand. Original problem: servicing aircraft 12 Constructing the network: part 1 0 New napkins are shipped from node 0 j New napkins are shipped to node j for j = 1 to 7. j’ Soiled napkins are shipped to node j’ for j’ = 1 to 7 8 Soiled napkins that are not cleaned are sent to node 8 0 1 2 3 4 5 6 7 1’ 2’ 3’ 4’ 5’ 6’ 7’ 8 flow on (j, j’) must be at least dj 13 Constructing the network: part 2 all nodes have b(j) = 0. 1-day laundry has a cost of b¢ 2-day laundry has a cost of c¢ Clean napkins can be used the next day. Whatever gets purchased eventually gets soiled and not cleaned 0 1 2 3 4 5 6 7 new 1’ 2’ 3’ 4’ 5’ 6’ 7’ soiled 8 14 Why do we need the arc (8, 0)? z If we put a supply of D at node 0, it means that we will purchase exactly D napkins z But we don’t know how many napkins we will purchase. z So, we assume that each napkin purchased is eventually left unclean. z Then the flow out of 0 is the flow into 8. z The arc (8, 0) returns the flow from 8 to 0. 15 Bipartite Graph N1 N2 Bipartite Digraph N1 N2 1 5 1 5 2 6 2 6 3 7 3 7 4 8 4 8 In a bipartite graph G = (N, A), the node set N is partitioned into two parts N1, and N2. All arcs (i, j) have i ∈ N1 and j ∈ N2. 16 The Transportation Problem: the min cost flow problem on a bipartite graph and with no arc capacities. •3 warehouses: nodes 1, 2, 3 W 6 •3 retailers: nodes 4, 5, 6 R 0 1 1 4 4 1 •Demand for goods at the warehouses (4, 8 and 3) Lower bound on flow 1 7 2 2 5 8 1 2 3 •Supplies of goods at the warehouses (6, 7 and 2) : Upper bound on flow 1 0 1 6 3 •Costs on shipping from each warehouse to each retailer •Constraints for this problem. Send exactly the supply, satisfy demand exactly, and minimize cost. Next: the LP for this transportation problem. 17 The constraints for the transportation problem W 6 R 0 1 1 1 4 4 1 7 2 2 5 8 6 3 1 2 3 1 0 1 x14 x15 x16 x24 x25 x26 x34 x35 x36 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 = = = = = = 6 7 2 4 8 3 xij ≥ 0 for i = 1, 2, 3 and j = 4, 5, 6 This graph is bipartite. That is, the nodes are partitioned into two parts and arcs have one endpoint in each part. 18 This constraint matrix is a node arc incidence matrix in disguise. W 6 R 0 1 1 1 4 4 1 7 2 2 5 8 6 3 1 2 3 1 0 1 x14 x15 x16 x24 x25 x26 x34 x35 x36 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 -1 1 0 0 -1 1 0 0 -1 1 0 0 0 -1 1 0 0 -1 1 0 0 -1 1 0 0 0 -1 1 0 0 -1 1 0 0 -1 1 = = = = = = 6 7 2 -4 4 -8 8 -3 3 xij ≥ 0 for i = 1, 2, 3 and j = 4, 5, 6 Multiply rows for R by -1. Result: a 1 and a -1 in each column. 19 Formulation Exercise. Grading 3 TAs need to determine how to allocate the grading of a midterm over two different sections of the class. Each TA can grade 40 different students. The sizes of the two sections are 50 and 70. The TAs have specified utility for grading. • Section 1 Section 2. TA1 9 6 TA2 5 7 TA3 8 9 z Problem: find the allocation of midterms to the TA’s so as to maximize the utility of the graders. Formulate as an LP. 20 The Transportation Problem: a very specific network model z z z z z z n1 supply nodes n2 demand nodes Sum of supplies = sum of demands No arc capacities Each arc is from a supply node to a demand node minimize cost of shipping from supply nodes to demand nodes 21 The Transportation Problem In general the LP formulation is given as m Minimize n ∑∑ c i =1 j =1 All arcs are from a supply node to a demand node. n ∑x j =1 ij ij xij = ai , ∀i = 1,… , m m supply nodes m ∑ xij = b j , ∀j = 1,…, n i =1 n demand nodes xij ≥ 0, ∀ij 22 The shortest path problem 2 2 4 3 Find the shortest path from node 1 to node 5. 1 1 3 5 3 5 3 Translation to flow problem: Node 1 has a supply of 1. Node 5 has a demand of 1. 1 2 2 4 3 1 1 3 5 The optimal solution will send a flow of 1 unit along the shortest path from node 1 to node 5. 3 3 5 -1 23 The flow constraints 2 4 3 1 1 1 3 5 x12 + x13 = 1 x23 + x24 - x12 = 0 x35 - x13 - x23 = 0 x45 - x24 = 0 -x35 - x45 = -1 xij ≥ 0 for all (i, j) ∈ A. 3 5 3 1 This formulation works so long as there is no cycle with negative cost. -2 7 6 1 -1 8 24 Row sums Matrix Fill In Column sums ? 5 1 ? 1 16 2 ? ? ? 1 16 1 1 ? ? ? 11 ? ? 2 5 1 20 1 1 3 ? ? 6 13 19 13 17 7 Is it possible to fill in the missing data with non-negative integers and have the row sums and column sums as specified? If so, how large or small can be the element in position 2,3? How is this a transportation problem? 25 Matrix Fill In Rows entry in (i,j) is “flow” Minimize X23 Columns 9 1 1 9 13 2 2 12 9 3 3 7 12 4 4 12 1 5 5 4 ? 5 ? 1 ? 1 ? 2 ? 1 1 1 ? ? ? ? ? 2 5 1 1 9 13 1 12 19 3 7 13 ? 12 17 ? 4 7 16 9 16 13 11 13 9 20 12 6 1 Determine the row and column sums for unknown entries. Formulate a transportation problem Transportation Problem 26 An Assignment Problem: flows representing assignments,or one-to-one mappings •3 persons: nodes 1, 2, 3 P 1 •3 tasks: nodes 4, 5, 6 T 0 1 1 4 1 •Each task has a person assigned 1 •Utility of assigning a person to a task 1 1 2 2 5 1 6 1 1 1 3 •Each person must be assigned to a task 1 0 1 •Objective: meet constraints while maximizing total utility 27 An Assignment Problem There will be three arcs with 1 unit of flow. W 1 R 0 1 1 W 4 1 1 1 5 1 1 2 R 1 4 1 5 1 6 1 1 1 1 2 2 1 1 3 1 0 1 1 1 6 1 1 3 A solution may be viewed as an “Assignment” 28 The Assignment Problem It is a special case of the transportation problem where all demands and supplies are 1. z z z z z z n persons n tasks uij = utility of assigning person i to task j Maximize the sum of the utilities Each person gets assigned to a task Each task has one person assigned to it. 29 The Assignment Problem z Suppose that n persons (labeled 1 to n) are assigned to n tasks (also labeled 1 to n) z Let xij = 1 if person i is assigned to task j z Let xij = 0 if person i is not assigned to task j z Let uij be the utility of assigning person i to task j z Exercise: formulate the assignment problem for the 3 x 3 case. 30 The Assignment Problem In general the LP formulation is given as n Minimize n ∑∑ c i =1 j =1 n ∑x j =1 ij ij xij = 1, ∀i = 1,… , n Each supply is 1 n ∑ xij = 1, ∀j = 1,… , n Each demand is 1 i =1 xij = 0 or 1, ∀ij Special case of the transportation problem. 31 Comments on the Assignment Problem z The Air Force has used this for assigning thousands of people to jobs. z This is a classical problem. Research on the assignment problem predates research on LPs. z Very efficient special purpose solution techniques exist. – 13 years ago, Yusin Lee and J. Orlin solved a problem with 2 million nodes and 40 million arcs in ½ hour. ] – We could do better today. The Assignment Problem in color 32 Some More on the Assignment Problem 1 7 2 8 3 9 4 10 5 11 6 12 There are 6! different assignments. There are n! different assignments in an n x n assignment problem. Diverse applications. 33 An Application of the Assignment Problem Suppose that there are moving targets in space. You can identify each target as a pixel on a radar screen. Given two successive pictures, identify how the targets have moved. This may be the most efficient way of tracking items. 34 Conclusions. z Advantages of the transportation problem and the minimum cost flow problem – Integer solutions – Very fast solution methods – Extremely common in modeling 35 Summary z Minimum Cost Flows – – – – – shortest paths transportation problem assignment problem plus more important subproblem of many optimization problems, including multicommodity flows 36 Baseball Elimination Problem Games Games Won Left Bos Chi Atl. Den. Bos 82 9 Bos -- 1 7 1 Chi 79 4 Chi 1 -- 0 3 Atl. 77 8 Atl. 7 0 -- 1 Denver 76 5 Den. 1 3 1 0 Has Chicago already been eliminated from winning in this hypothetical season finale? Has Atlanta? 37 Modeling as an optimization problem xAB = number of wins by Atlanta over Boston 7- xAB = number of wins by Boston over Atlanta xAD = number of wins by Atlanta over Denver 1- xAD = number of wins by Denver over Atlanta xBC = … xBD = … xCD = … Bos Chi Atl. Den. Bos -- 1 7 1 Chi 1 -- 0 3 Atl. 7 0 -- 1 Den. 1 3 1 0 38 Games Games Won Left Bos 82 9 8 Chi 79 4 0 Atl. 77 8 6 Denver 76 5 7 AB AD Bos 7-xAB+ Chi -- -- Atl. xAB +xAD Den. Determining whether Chicago can win the championship, assuming Chicago wins all of its games, and thus has 83 wins. BD . RHS +xBD ≤ 1 -- -- -- ≤ 6 ≤ 7 1-xAD + 1 - xBD and also upper and lower bound constraints. 39 The constraint matrix is a node-arc incidence matrix AB AD Bos 7-xAB+ Atl. xAB Den. BD . RHS +xBD ≤ 1 ≤ 6 ≤ 7 +xAD 1-xAD + 1 - xBD xAB xAD xBD . RHS Bos -1 0 +1 ≤ -6 Atl. 1 1 0 ≤ 6 Den. 0 -1 -1 ≤ 5 The baseball elimination problem is a minimum cost flow problem in disguise. 40