Optimization Methods Network Optimization - Introduction and Applications

1 Network Optimization What is a network? Slide 1 2 Networks 2.1 Formally Slide 2 2.2 Electrical & Power Network Slide 3 2.3 Road Network Slide 4 2.4 Airline Route Map Slide 5 2.5 Internet Backbone Slide 6 2.6 Printed Circuit Board Slide 7 2.7 Surface Meshes Slide 8 3 Common Thrust Move some entity (electricity, a consumer product, a person, a vehicle, a message, . . . ) from one point to another in the underlying network, as eciently as possible. Lecture 1: Learn how to model application settings as network ow problems. Lecture 2: Study ways to solve the resulting models. 1 Slide 9 4 Outline 4.1 Today's Lecture � � � � � Network ow problems Applications of the shortest path problem Applications of the maximum ow problem Applications of the minimum cost ow problem Extended models Slide 10 5 Shortest Path 5.1 Description Identify a shortest path from a given source node to a given sink node. � � � Slide 11 Finding a path of minimum length. Finding a path taking minimum time. Finding a path of maximum reliability. 6 Maximum Flow 6.1 Description Determine the maximum ow that can be sent from a given source node to a sink node in a capacitated network. 2 Slide 12 Determining maximum steady-state flow of � petroleum products in a pipeline network, � cars in a road network, � messages in a telecommunication network, � electricity in an electrical network. 7 Min-Cost Flow 7.1 Description Determine a least cost shipment of a commodity through a network in order to satisfy demands at certain nodes from available supplies at other nodes. Arcs have capacities and cost associated with them. � � � � Slide 13 Distribution of products. Flow of items in a production line. Routing of cars through street networks. Routing of telephone calls. 7.2 In LOP Form Slide 14 Network G = (N A). Arc costs c : A ! Z . Arc capacities u : A ! N . Node balances b : N ! Z . min s.t. X cij xij 2A X xij ;(i j)X xji = xij xij   j:(i j)2A j:(j i)2A 3 bi for all i 2 N uij for all (i j ) 2 A 0 for all (i j ) 2 A 8 Shortest Path 8.1 Interword Spacing in LATEX Slide 15 8.2 Interword Spacing in LATEX (2) Slide 16 The spacing between words and characters is normally set automatically by LATEX. Interword spacing within one line is uniform. LATEX also attempts to keep the word spacing for di erent lines as nearly the same as possible. The paragraph consists of n words, indexed by 1 2 : : : n. cij is the attractiveness of a line if it begins with i and ends with j ; 1. (LATEX uses a formula to compute the value of each cij .) For instance, c12 = ;10 000 c14 = 100 ::: c13 = ;1 000 c1 37 = ;100 000 8.3 Interword Spacing in LATEX (3) Theorem 1 Slide 17 The problem of decomposing a paragraph into several lines of text to maximize total attractiveness can be formulated as a shortest path problem. 9 Shortest Path 9.1 Dynamic Lot Sizing T periods of demand for a product. The demand is dt > 0 in period t. Let xt be the production in period t (to be determined). Production cost ft (xt ) = at + bt xt . Let It be the inventory carried from period t to period t + 1. ht It linear cost of carrying inventory. What is the minimum cost way of meeting demand? 4 Slide 18 9.2 Dynamic Lot Sizing (2) Slide 19 Lemma 1 There is exactly one arc with positive ow directed into each node t > 0. 9.3 Dynamic Lot Sizing (3) Corollary 1 Production in period s satises demands exactly in periods s s + 1 : : : t, Slide 20 for some t. 9.4 Dynamic Lot Sizing (4) Theorem 2 The optimal production and inventory schedule can be determined by solving a shortest path problem. 5 Slide 21 Let cst be the cost of producing in period s to meet demands in periods s s + 1 : : : t ; 1 (including cost of inventory). 10 Maximum Flow 10.1 Baseball Elimination http://riot.ieor.berkeley.edu/b~aseball/ 10.2 Baseball Elimination (2) Team 0 is \our" team (e.g., Boston Red Sox). There are other teams. = number of wins team has so far. = number of games left between teams and . Our team is eliminated if, for all possible ways of playing out the rest of the season, there is always another team that ends up with more wins than our team. Slide 22 Slide 23 n wi i gij i j 10.3 Baseball Elimination (3) Nodes for each team i 6= 0, for every pair fi j g of teams (i j 6= 0), source s, and sink t. Arcs: (i fi j g) with capacity +1. (s i) with capacity w0 + j g0j ; wi. (fi j g t) with capacity gij . Interpretation: Flow on arc (i fi j g) = # of remaining games with j that i wins. Slide 24 P 10.4 Baseball Elimination (4) Theorem 3 There is a
ow saturating if and only if there is a way to play t Slide 25 out the season where Team 0 is not eliminated. 10.5 Max-Flow vs. Min-Cut What is the value of the max ow in this network? 10.6 Max-Flow vs. Min-Cut (2) An (s t)-cut in a network G = (N A) is a partition of N into two disjoint subsets S and T such that s 2 S and t 2 T . The capacity of a cut (S T ) is i2S j2T uij . P P Theorem 4 The value of a maximum ( )-
ow is equal to the capacity of a s t minimum (s t)-cut. 6 Slide 26 Slide 27 10.7 Open Pit Mining http://riot.ieor.berkeley.edu/riot/Applications/OPM/ Slide 28 10.8 Open Pit Mining (2) 10.8.1 Small Example Slide 29 11 Maximum Flow 11.1 Open Pit Mining (3) There is a 1 : 1-correspondence between feasible sets of blocks and (s t)-cuts of nite capacity. A feasible set B of blocks corresponds to the cut fsg  B . The weight of a feasible set B of blocks is w(B ) = i2B+ wi ; i2B; jwij. The capacity of the cut fsg  B is i2B+ wi + i2B; jwi j. P Hence, w(B ) + cap(fsg  B ) = P P Slide 30 P Pi:w >0 wi. i 12 Min-Cost Flow 12.1 Passenger Routing United Airlines has seven daily ights from BOS to SFO, every two hours, starting at 7am. Capacities are 100, 100, 100, 150, 150, 150, and 1. Passengers su ering from overbooking are diverted to later ights. Delayed passengers get $200 plus $20 for every hour of delay. Suppose that today the rst six ighs have 110, 160, 103, 149, 175, and 140 conrmed reservations. Slide 31 Determine the most economical passenger routing strategy! 12.2 Postman Problem Identify a walk of minimum length that starts at some node, traverses each arc at least once, and returns to the starting node. patrolling streets by police, routing of street sweepers, fuel oil delivery to households, spraying of roads (with sand during snowstorms), ... 7 Slide 32 12.3 Postman Problem (2) In an optimal walk, a postal carrier might traverse arcs more than once. Any carrier walk must satisfy the following conditions: xij ; xji = 0 for all i 2 N X X j:(i j)2A j:(j i)2A xij � 1 Slide 33 for all (i j ) 2 A Here, xij is the # of times the carrier traverses arc (i j ). If we get x, how can we reconstruct a walk? 13 Network Optimization 13.1 Further Models � � � � � � � � Minimum spanning tree problems, Matching problems, Generalized ow problems, Multicommodity ow problems, Constrained shortest path problems, Unsplittable ow problems, Network design problems, . .. 8 Slide 34