Report

Network Transportation Assignment Shortest Path OPL In Class . Lecture 09: Network Programming I . Seeronk Prichanont1 Wipawee Tharmmaphornphilas1 Oran Kittithreerapronchai1 1 Department of Industrial Engineering, Chulalongkorn University Bangkok 10330 THAILAND last updated: February 10, 2014 OR I Network I – v1.0 1/ 37 Network Transportation Assignment Shortest Path OPL In Class Outline 1. 2. 3. 4. 5. 6. Importance of Network Programming Transportation & Transhipment Problem Assignment Problem Shortest Path Problems Solving Network Programming with OPL: Refinery Problem In-Class Exercise OR I Network I – v1.0 2/ 37 Network Transportation Assignment Shortest Path OPL In Class What is Network Programming? What: Network Programming is a set of LP problem that can represent by Graph: Nodes and Arcs Example: transhipment, shortest path, max-flow, min-spanning tree, assignment Why do we care about Network Problem? Its applications are frequently emerged Special structure that is easy to solve Under ’right’ condition → integer solution for free OR I Network I – v1.0 3/ 37 Network Transportation Assignment Shortest Path OPL In Class Applications of Network Programming Physical Networks road networks railway networks airline traffic networks electrical networks, e.g., the power grid Abstract networks project chart multi-period inventory problem OR I Network I – v1.0 4/ 37 Network Transportation Assignment Shortest Path OPL In Class Introduction to Graph Theory 1 4 2. 3 Node: (vertex) presentation of stage N ∈ {1, 2, 3, 4} Edge: (arc) connecting line between nodes E ∈ {(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)} OR I Network I – v1.0 5/ 37 Network Transportation Assignment Shortest Path OPL In Class Parameters in Graph -10 1 15 15, $2 4 -20 30, $2 8, $4 ∞, $5 2. 10, $1 3 15 Demand/Suppy: demands and supply at each node, e.g. demands at node 1 is 10 Cost: incurred cost per a unit of flow, e.g., cost at edge (1, 2) is 5 Capacity: unit flow allow at each edge, e.g., flow at edge (1, 2) must be less than ∞ OR I Network I – v1.0 6/ 37 Network Transportation Assignment Shortest Path OPL In Class Example of Graph representation A network with 6 vertices, N ∈ {1, 2, 3, 4, 5, 6}, and {−12, 24, −14, −16, 30, −12} demands/suppies at vertices and the following cost and capacity at each edge. Construct the graph of this network Edge (1,2) (2,4) (4,6) (5,6) (3,5) (1,3) (1,5) (2,3) (2,6) (4,5) OR I Network I – v1.0 Cost $2 $2 $2 $2 $2 $2 $5 $1 $5 $1 Max Capacitiy 6 6 6 6 6 6 2 ∞ 2 ∞ 7/ 37 Network Transportation Assignment Shortest Path OPL In Class Graph Representation 24 -16 2 4 -12 1 6 -12 3 5 -14 30 . . Convention signs . demand node = negative balance / inflow = negative coefficient . supply node = positive balance / outflow= positive coefficient OR I Network I – v1.0 8/ 37 Network Transportation Assignment Shortest Path OPL In Class Network Terminology OR I Network I – v1.0 9/ 37 Network Transportation Assignment Shortest Path OPL In Class Transportation Problems Idea: Find the minimal total shipping cost with supply and demand limits Observation: Two types of nodes: sources and destinations Special algorithm: Transportation Simplex (Northwest corner) Applications: Minimize the total postal shipment costs Minimize the total costs in production process Related problems: Bipartite Matching problem: Transhipment problem: consisting of transit node (’0’ balance) OR I Network I – v1.0 10/ 37 Network Transportation Assignment Shortest Path OPL In Class PowerCo Problem: Transmission Problem Powerco has three power plants and must serve four cities with electricity supplies/demands and transmission costs as follows: To From Plant 1 Plant 2 Plant 3 Demand (million kw-hr) City 1 $8 $9 $14 45 City 2 $6 $12 $9 20 City 3 $10 $13 $16 30 City 4 $9 $7 $5 30 Supply (million kw-hr) 35 50 40 Construct the graph representative of this network source: Winston. 2003. Section 7.Ex01 pp. 360 OR I Network I – v1.0 11/ 37 Network Transportation Assignment Shortest Path OPL In Class PowerCo Problem: Network 35 50 40 -45 2 -20 3 -30 4 -30 2 3. Plants OR I Network I – v1.0 1 1 Cities 12/ 37 Network Transportation Assignment Shortest Path OPL In Class Non-Balanced Transportation Problems . If . total supplies ̸= total demands, introducing dummy node In PowerCo problem, if plant 2 can generate only 40 million kw-hr (instead of 50 million kw-hr). 35 1 1 -45 40 2 2 -20 40 3 3 -30 . Plants OR I Network I – v1.0 4 -30 Cities 13/ 37 Network Transportation Assignment Shortest Path OPL In Class Boralis Problem: Production-Inventory Problem Boralis manufactures backpacks for serious hiker. Boralis estimates the demand for the four months to be 100, 200, 180 and 300 units. Boralis can produce 50, 180, 280, and 270 units during month one to four. In addition, The production cost per backpack is 40 The additional holding cost is $0.5 per backpack per month The additional penalty cost is $2 incurred per backpack per month delay Determine the optimal production schedule for the four months source: Winston. 2003. Section 7.Ex01 pp. 328 OR I Network I – v1.0 14/ 37 Network Transportation Assignment Shortest Path OPL In Class Boralis Problem: Network 50 -100 S1 D1 180 -200 S2 D2 280 S3 OR I Network I – v1.0 -180 . D3 270 -300 S4 D4 source: production dest: demand 15/ 37 Network Transportation Assignment Shortest Path OPL In Class Widgetco Problem: Transhipment Problem Widgetco manufactures at two factories, located in Memphis and Denver, and ships widgets to two customer, located in LA and Boston. Each customer demands 130 widgets per day. The company can either ship directly to a customer or ship through its two transit points: New York and Chicago. The transportation costs (in $ per widget) are listed as follows: From Memphis Denver New York Chicago New York 8 15 6 To Chicago 13 12 6 - LA 25 26 16 14 Boston 28 25 17 16 If the Memphis and Denver factories have daily production of 150 and 200 widgets per day. source: Winston. 2003. Section 7.Ex05 pp. 400 OR I Network I – v1.0 16/ 37 Network Transportation Assignment Shortest Path OPL In Class Widgetco Problem: Network 150 0 -130 ME NY LA . OR I Network I – v1.0 200 0 -130 DE CH BO 17/ 37 Network Transportation Assignment Shortest Path OPL In Class Assignment Problems What: A special application of transportation problems Observation: all supplies equal 1; all demands equal 1 Decision{variable: ’0’ or ’1’ 1, if resouce i is assigned to object j xi,j = 0, otherwise. Trivial: generalization Bipartite matching OR I Network I – v1.0 18/ 37 Network Transportation Assignment Shortest Path OPL In Class Bidding School Bus Problem Four companies have made bids for school bus routes as follows: Company 1 2 3 4 Route 1 $4000 $3000 - Bids Route 2 Route 3 $5000 $4000 $2000 $4000 Route 4 $5000 $5000 If each company can be assigned only one route, formulate assignment problem to minimize cost of running the four bus routes source: Winston. 2003. Section 7.5.8 pp. 400 OR I Network I – v1.0 19/ 37 Network Transportation Assignment Shortest Path OPL In Class Bidding School Bus Problem: Graph . 1 -1 C1 R1 1 -1 C2 R2 1 -1 C3 R3 1 -1 C4 R4 If each company can be assigned up to two routes, formulate assignment problem to minimize cost of running the four bus routes OR I Network I – v1.0 20/ 37 Network Transportation Assignment Shortest Path OPL In Class Machine Scheduling Problem source: Winston. 2003. Section 7.Ex04 pp. 400 OR I Network I – v1.0 21/ 37 Network Transportation Assignment Shortest Path OPL In Class Machine Scheduling Problem: Graph . OR I Network I – v1.0 1 -1 M1 J1 1 -1 M2 J2 1 -1 M3 J3 1 -1 M4 J4 22/ 37 Network Transportation Assignment Shortest Path OPL In Class Shortest Path Problems Idea: Find a shortest path through the network that starts at an origin (source) node to a destination (sink)node Observation: Each edge has cost that incurs when used, but no capacity Special algorithm: Dijkstra’s alorithm which can find the shortest paths from one node to all others in a graph with non-negative arc lengths. Applications: Minimize the total distance traveled Minimize the total cost of a sequence of activities Minimize the total time of a sequence of activities OR I Network I – v1.0 23/ 37 Network Transportation Assignment Shortest Path OPL In Class Example of Shortest Path Problem $3 2 4 $2 $4 Plant $2 1 6 $3 City $2 $3 3 5 . OR I Network I – v1.0 24/ 37 Network Transportation Assignment Shortest Path OPL In Class Library Shelving Problem A library must build shelves to store 200 4-inch high books, 100 8-inch high books, and 80 12-inch high books. Each book is 0.5 inch thick. Each shelve costs $2,300 to build a shelf and $5 per square inch is incurred to store (Assume that storage area = book’s thickness × shelve hight). Formulate the problem as Shortest Path Problem. Shelves 4” 8” 8” 8” 12” 12” 12” Books 4” 8” 4”,8” 4” 12” 8”,12” 4”,8”,12” Building Costs $2300 $2300 $2300 $2300 $2300 $2300 $2300 Storage Costs $2,000 $2,000 $6,000 $4,000 $2,400 $5,400 $11,400 Un-shelved 8”, 12” 4”, 12” 12” 8”, 12” 4”, 8” 4” - source: Winston. 2003. Section 8.2.8 pp. 419 OR I Network I – v1.0 25/ 37 Network Transportation Assignment Shortest Path OPL In Class Library Shelving Problem: Network $8.3 1 $7.7 0 $4.3 0 . OR I Network I – v1.0 0 $4.3 4 -1 $4.7 8 12 $13.7 26/ 37 Network Transportation Assignment Shortest Path OPL In Class RentCar Problem RentCar is developing a 4-year planning horizon replacement plan for its car fleet. At the start of each year, RentCar must decide whether a car should be kept or replaced. A car must be in service between 1 year to 3 years. The cost associated with the replacement at each year are listed as follows: Year acquired year 1 year 2 year 3 year 4 Replacement cost ($1000) at year 1 2 3 4.0 5.4 9.8 4.3 6.2 8.7 4.8 7.1 4.9 - Formulate RentCar problem as a shortest path problem. OR I Network I – v1.0 27/ 37 Network Transportation Assignment Shortest Path OPL In Class RentCar Problem: Network 1 0 0 0 -1 Y1 Y2 Y3 Y4 Y5 . OR I Network I – v1.0 28/ 37 Network Transportation Assignment Shortest Path OPL In Class OPL for Network Problem Easy: Network constraints are the same (balancing or capacity) Efficient: Graph may be sparse (many nodes, but few edges) → tuple tuple: Custom Data Structure Idea: tell OPL exact edges and its data used in model What: custom data (edge, cost, max capacity, min capacity) For: sparse graph How: input table contained all data (edge, cost, max capacity, min capacity) extract set of edge, cost, max, and min of each edge OR I Network I – v1.0 29/ 37 Network Transportation Assignment Shortest Path OPL In Class Oilco Refinery: Transhipment Problem Oilco has two oil fields (Los Angeles and San Diego), two uncapacitated refineries (Dallas and Houston), and two customers (New York and Chicago). Each parties has demands, supply, and transportation cost as follows. City Los Angeles San Diego Dallas Houston New York Chicago From Los Angeles San Diego Dallas Houston Demand/Supply Cost (100,000 barrels) ($ per 100,000 barrels) 4 5 0 700 0 900 -3 -4 To ($ per 100,000 barrels) Dallas Houston New York Chicago 300 110 420 100 450 550 470 530 source: Winston. 2003. Section 8.5.5 pp. 455 OR I Network I – v1.0 30/ 37 Network Transportation Assignment Shortest Path OPL In Class OilCo Refinery: Network 4 0 -3 L D N 5 0 -4 S H C -2 . Field OR I Network I – v1.0 dummy Refinery Customer 31/ 37 Network Transportation Assignment Shortest Path OPL In Class “tuple”: Tool for Sparse Matrix Idea: list/create DVs and parameters only what we need Example: tuple DataTuple = { string o; string d; float cost; }; {DataTuple} Data = ...; tuple ConnectionTuple = { string o; string d; }; {ConnectionTuple} Connection = { < o,d > | < o,d,cost > in Data } ; {float } transCosts[Connection] = [ < aData.o,aData.d >:aData.cost | aData in Data]; {float } demands[Connection] = ...; OR I Network I – v1.0 32/ 37 Network Transportation Assignment Shortest Path OPL In Class Oilco Refinery: Notation Cities = {L,S,D,H,N,C ,dummy } ; {string } Cities = ...; z}|{ N = {<o,d>|<o,d,cost> in Data} ; {ConnectionTuple} Connection = z}|{ E = = float operCosts[Cities] = ...; z}|{ oi etc.]# z }| { demands/supplies at node ; [<aData.o,aData.d>:aData.cost|aData in Data] ; float+ transCosts[Connection] = z}|{ ci,j z }| { set of edges demands = #[L:4, S:5, D:0, float demands[Cities] =... ; z}|{ Di z }| { set of vertices = z }| { transportation costs at edge (i, j) operCosts = #[D:700, H:900]# ; z }| { = operation cost at node i dvar float+ flow [Connection] ; z}|{ xi,j OR I Network I – v1.0 = costs at edge (i, j) 33/ 37 Network Transportation Assignment Shortest Path OPL In Class Oilco Refinery: Formulation sum(<o,d> in Connection) (transCosts[<o,d>]+operCosts[o]) ∗ flow [<o,d>]; dexpr float objective max z}|{ z }| { z∑ = z }| { (ci,j + oi )xi,j (i,j)∈ E s.t. sum(<o,c> in Connection) z∑ }| { (i,c)∈ E OR I Network I – v1.0 sum(<c,d> in Connection) flow [<o,c>] z }| { −xi,c + z∑ }| { demands[c] flow [<c,d>] z}|{ xc,j = z}|{ Dc forall(c in Cities) z }| { ∀c∈ N (c,j)∈ E 34/ 37 Network Transportation Assignment Shortest Path OPL In Class Oilco Refinery: OPL model file OR I Network I – v1.0 35/ 37 Network Transportation Assignment Shortest Path OPL In Class Oilco Refinery: OPL data file OR I Network I – v1.0 36/ 37 Network Transportation Assignment Shortest Path OPL In Class Job Assignment Problem A company needs to assign 6 different jobs to 6 workers. Each worker has different skills and may not be suitable for a particular job. Based on past experience, the supervisor estimates the time for each worker to complete each job in minute as follow : Worker/Job A B C D E F 1 9 8 - 2 15 10 3 10 13 - 4 14 16 14 5 11 15 13 - 6 10 6 Formulate mathematical programming to minimize total times OR I Network I – v1.0 37/ 37