Network Models - Shortest Path and Transshipment

Network Models II Shortest Path Cross Docking Enhance Modeling Skills Modeling with AMPL The Shortest Path Model aFind the shortest path from Home to 5 H 8 7 H 1 2 3 4 3 1 3 4 1 1 6 6 5 1 2 3 2 Direction aTwo-way streets aOne-way streets H 8 7 H 1 2 3 4 3 1 3 4 1 1 6 6 5 1 2 3 2 03ShortestPathModel.xls Shortest Path Model Connectivity From\To Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home 1 1 1 Site 1 1 1 1 Site 2 1 1 1 Site 3 1 1 1 Site 4 1 1 1 1 Site 5 1 1 1 Site 6 1 1 1 Site 7 1 1 1 Route From\To Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Total To 0 0 0 0 0 0 0 0 Total From Total To 0 0 0 0 0 0 0 0 Net Required 1 -1 0 0 0 0 0 0 Distance From\To Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home 4 7 8 Site 1 4 6 1 Site 2 6 1 2 Site 3 1 1 1 Site 4 7 1 3 2 Site 5 2 3 3 Site 6 3 1 3 Site 7 8 2 1 Total From 0 0 0 0 0 0 0 0 Total Distance Home Site 1 Site 2 Site 3 Site 4 Site 5 Site 6 Site 7 Home 0 0 0 0 0 0 0 0 Site 1 0 0 0 0 0 0 0 0 Site 2 0 0 0 0 0 0 0 0 Site 3 0 0 0 0 0 0 0 0 Site 4 0 0 0 0 0 0 0 0 Site 5 0 0 0 0 0 0 0 0 Site 6 0 0 0 0 0 0 0 0 Site 7 0 0 0 0 0 0 0 0 Total To 0 0 0 0 0 0 0 0 Total From 0 0 0 0 0 0 0 0 0 Challenge aBuild a Solver model A Solver Model aThe Objective: Minimize $U$21 aThe Variables: $C$13:$J$20 aThe Constraints: Only travel on existing edges $C$13:$J$20 <= $C$3:$J$10 Number From - Number To = Net Required $C$22:$J$22 = $C$23:$J$23 Flow Conservation aNumber From - Number To = Net Required a Number of times - Number of = ? we leave times we enter a+1 at Home (we leave once) a-1 at Site 5 (we arrive once) a0 everywhere else each time we arrive (if ever), we leave Compare with Assignment Model aAssignment Model Sum across each row =1 Sum down each column =1 Each variable appears in 2 constraints aShortest Path Model Sum across a row - Sum down the column = 0 Trips out of a site - Trips into the site Each variable appears in ? constraints Network Flow Problems aEach variable appears in at most two constraints At most one constraint as - the variable At most one constraint at + the variable aAssignment Sum across each row = 1 Sum down each column =1 aShortest Path Sum across the a row - sum down the col = # Bounds aVariables can also have bounds e.g., in the Shortest Path Model: Number of times we use each variable Lower bound: >= 0 Upper bound: <= 1 if it is an edge, 0 otherwise Properties of Network Flows aIf the bounds and RHS are integral, the solution will be integral aIt the costs are integral, the reduced costs and marginal values will be integral aCan be solved very quickly aLimited demands on memory Crossdocking a3 plants a2 distribution centers a2 customers aMinimize shipping costs A Network Model Minimum Cost Network Flow Problem Unit Shipping Costs Transportation Costs ($ 000/Ton) Plant to DC 1 DC 2 DC Plant 1 $ 5.0 $ 5.0 Plant 2 $ 1.0 $ 1.0 Plant 3 $ 1.0 $ 0.5 DC to Customer Customer 1 $ Customer 2 $ DC 1 2.0 $ 12.0 $ Arc Capacities Transportation Capacities Costs Capacities Flows Payments Costs Flows Payments DC 2 2.0 12.0 Shipments Plant to DC Plant 1 Plant 2 Plant 3 DC 1 200 200 200 DC 2 200 200 200 DC to Customer Customer 1 Customer 2 DC 1 200 200 DC 2 200 200 Payments Plant to DC Plant 1 Plant 2 Plant 3 Total In DC 1 - DC 2 - Total Out - Total In - DC 2 - Supply 200 300 100 DC 1 - $ $ $ $ DC 2 - DC to DC 1 Customer Customer 1 $ Customer 2 $ Total In $ - $ $ $ DC 2 - Plant to DC Plant 1 Costs Plant 2 Capacities Plant 3 Flows Total In $ $ $ $ Total $ $ $ $ Out - Costs DC to Capacities Customer Payments Customer 1 Customer 2 Total Out Net Flow DC 1 DC 1 - Demand 400 180 DC 2 - Total Shipping Cost $ - Total $ $ $ Out - Challenge aBuild a Solver Model A Solver Model aObjective: Minimize $K$28 aVariables: $C$17:$D$19, $C$23:$D$24 aConstraints: Do not exceed supply at the plants $E$17:$E$19 <= $F$17:$F$19 Meet customer demand $E$23:$E$24 >= $F$23:$F$24 Do not exceed shipping capacity $C$17:$D$19 <= $K$6:$L$8 and $C$23:$D$24 <= $K$11:$L$12 And... aFlow conservation at the DCs $C$28:$D$28 = 0 aSupply and Demand like Autopower aFlow conservation at DCs like Shortest Path Network Flows: Good News aLots of applications aSimple Models aOptimal Solutions Quickly aIntegral Data, Integral Answers Network Flows: Bad News aUnderlying Assumptions Single Homogenous Product Linear Costs No conversions or losses ... Homogenous Product Must be able to interchange positions of product anywhere 15.057 Spring 03 Vande Vate 19 Linear Costs aNo Fixed Charges aNo Volume Discounts aNo Economies of Scale Summary aNetwork Flows Simple Formulation Flow Out (sum across a row) <= Capacity Flow In (sum down a column) >= Demand Flow In - Flow Out = Constant Limited by Homogenous Product Linear Costs etc. Integer Data give Integral Solutions Modeling with AMPL a Problems with Excel Solver Integration of “Model” and Data Example: Change the time horizon of our Inventory Model Excel is a limited database tool a Algebraic Modeling Languages Separate the “Model” from the Data Keep the data in databases How they work Conceptual Model Data Algebraic Modeling Language AMPL/OPL/GAMS/XPress/... Optimizer CPLEX OSL XPress Why AMPL aEstablished in US aVery good book aLower barrier to entry aFree “student” version aIndustrial strength tool Our Use of AMPL aPseudo AMPL to discuss models In class In exams aNeed to be precise about What’s a parameter, variable, … Indexing: relationships between variables, data, constraints aChallenges and Project Is this necessary/valuable? aAMPL is very detailed Expect 1 or 2 per team to master Rest to read and understand aBrings out the real issues Practical implementation -- you can oversee Data issues -- the real challenge aValuable tool The Transportation Model aset ORIG; aset DEST; aparam supply {ORIG}; aparam demand {DEST}; aparam cost {ORIG, DEST}; avar Trans {ORIG, DEST} >= 0; Transportation Model minimize Total_Cost: sum{o in ORIG, d in DEST} cost[o,d]*Trans[o,d]; s.t. Supply {o in ORIG}: sum{d in DEST} Trans[o,d] <= supply[o]; s.t. Demand {d in DEST}: sum{o in ORIG} Trans[o,d] >= demand[d]; The Data aAn Access Database called TransportationData.mdb aTables in the database Origin Supply Origins: Supply information Amsterdam 500 Antwerp 700 The Hague 800 Destinations: Demand information Destination Demand Leipzig Liege Nancy Tilburg 400 200 900 500 The Costs aCost: Unit transportation costs origin Amsterdam Amsterdam Amsterdam Amsterdam Antwerp Antwerp Antwerp Antwerp The Hague The Hague The Hague The Hague destination Leipzig Liege Nancy Tilburg Leipzig Liege Nancy Tilburg Leipzig Liege Nancy Tilburg cost 120 41 130 59.5 61 100 40 110 102.5 122 90 42 AMPL’s Output aAMPL reads the model and the data, combines the two and produces (in human readable form) … AMPLOutput.txt Produced by the command: expand >AMPLOutput.txt Reading Data table OriginTable IN "ODBC" "D:\Personal\15057\TransportationData.mdb" "Origins": ORIG <- [Origin], supply~Supply; Explanation: ‘table’ is a keyword that says we will read or write data ‘OriginTable’ is a name we made up. No other AMPL model entity can have this name ‘IN’ is a key word that says we are reading data. “ODBC” says we are using ODBC to read the data Explanation a "D:\Personal\15057\TransportationData.mdb” is the path to the database. Alternatively you can create a DSN (data source name) for this file, say TransportData, and use the command “DSN=TransportData”. a "Origins” is the name of the table in the database. Alternatively we can use an SQL command like “SQL=SELECT * FROM Origins” a The : is syntax. What follows is the mapping of the data we read to AMPL objects that will hold it. a The brackets [] around Origin mean that this field in the database indexes the data, e.g., 500 is the supply for Amsterdam. Explanation Continued aORIG <- [Origin] says that the values of the field Origin will define the set ORIG of origins asupply~Supply says that the values of the parameter supply should hold the values read from the field Supply in the database aread table OriginTable; reads the data. Reading Data table DestinationTable IN "ODBC" "D:\Personal\15057\TransportationData.mdb" "Destinations": DEST <- [Destination], demand~Demand; Explanation: a ‘table’ is a keyword that says we will read or write data a ‘DestinationTable’ is a name we made up. No other AMPL model entity can have this name a ‘IN’ is a key word that says we are reading data. a “ODBC” says we are using ODBC to read the data Explanation a "D:\Personal\15057\TransportationData.mdb” is the path to the database. Alternatively you can create a DSN (data source name) for this file, say TransportData, and use the command “DSN=TransportData”. a ”Destinations” is the name of the table in the database. Alternatively we can use an SQL command like “SQL=SELECT * FROM Destinations” a The : is syntax. What follows is the mapping of the data we read to AMPL objects that will hold it. a The brackets [] around Destination mean that this field in the database indexes the data, e.g., 400 is the demand for Leipzig. Explanation Continued aDEST <- [Destination] says that the values of the field Destination will define the set DEST of destinations ademand~Demand says that the values of the parameter demand should hold the values read from the field Demand in the database Reading Cost table CostTable IN "ODBC" "D:\Personal\15057\TransportationData.mdb" "Cost": [origin, destination], cost; Explanation: a ‘table’ is a keyword that says we will read or write data a ‘CostTable’ is a name we made up. No other AMPL model entity can have this name a ‘IN’ is a key word that says we are reading data. a “ODBC” says we are using ODBC to read the data Explanation a "D:\Personal\15057\TransportationData.mdb” is the path to the database. Alternatively you can create a DSN (data source name) for this file, say TransportData, and use the command “DSN=TransportData”. a ”Cost” is the name of the table in the database. Alternatively we can use an SQL command like “SQL=SELECT * FROM Cost” a The : is syntax. What follows is the mapping of the data we read to AMPL objects that will hold it. a The brackets [] around origin and destination mean that these two fields in the database index the data, e.g., 120 is the unit transportation cost from Amsterdam to Leipzig. Explanation Continued aWe don’t have an <- here, because we are not defining the members of a set. aWe read the values of the field cost in the database into the parameter cost. Note that since these two names are identical, we don’t need the ~. aread table CostTable; reads the data. Running AMPL amodel d:\15057\TransportationModel.mod; aoption solver cplex; # use cplex to solve asolve; adisplay Trans; Writing Output table TransOutTable OUT "ODBC" "D:\Personal\15057\TransportationData.mdb" "TransOut": {origin in ORIG, destination in DEST: Trans[origin, destination] > 0} -> [origin, destination], Trans[origin,destination]~Trans; write table TransOutTable; Explanation: a ‘table’ is a keyword that says we will read or write data a ‘TransOutTable’ is a name we made up. No other AMPL model entity can have this name Explanation a ‘OUT’ is a key word that says we are writing data. a “ODBC” says we are using ODBC to write the data a "D:\Personal\15057\TransportationData.mdb” is the path to the database. Or you can use “DSN=…” a "TransOut” is the name of the table to create. AMPL drops and writes this table. Any data currently in the table is lost. a : is syntax. It separates the description of the destination from the definition of the data and the mapping of the columns More Explanation a {origin in ORIG, destination in DEST: Trans[origin, destination] > 0} defines the index set that will control the data to write out. This says to only report on origin-destination pairs where we actually send a positive flow. a -> is syntax. It separates the indexing from the data definition and mapping to fields of the output table. a [origin, destination] indicates that the records of the output table are indexed by the origin-destination pairs. AMPL will write a new record for each pair. a Trans[origin,destination]~Trans says to create a field called Trans in the table and to populate it with the values of the Trans variable. Explanation completed awrite table TransOutTable; actually writes the data. origin destination Trans 300 aThe output is: Amsterdam Leipzig Amsterdam The Hague The Hague The Hague Antwerp Liege Leipzig Tilburg Nancy Nancy 200 100 500 200 700