Systems Optimization Integer Programming

Integer Programming I Modeling with Integer Variables How the Solver Works Complexity 1 A Simple Example Steel Cable Company Integer Programming Example Products Profit/Ton Bands $50,000 Coils $60,000 Market Limit (Tons) Hours/Ton 3 3 2 4 Total Hours 12 2 An Integer Program 3 Coils Limit 2 Production Capacity 1 Bands Limit Coils 1 2 3 4 Bands 3 Branch & Bound 3 Node 0: The linear program Coils Limit 2 $50,000*3 + $60,000*0.7 = $192,000 Production Capacity 1 X Bands Limit Coils 1 2 3 4 Bands 4 Branching 3 2 1 Coils Upper Branch Coils ≥ 1 Lower Branch Coils ≤ 0 1 2 3 4 Bands 5 Bounding 3 $50,000*3= $150,000 2 1 Coils Upper Branch Coils ≥ 1 Node 1: Lower Branch Coils ≤ 0 1 2 X 3 4 Bands 6 Bounding 3 The best answer yields at least $50,000*3= $150,000 2 1 Coils Node 2: Upper Branch Coils ≥ 1 X Yields $188,571 Lower Branch Coils ≤ 0 1 2 3 4 Bands 7 Further Nodes 3 2 Node 3: Lower Branch Bands ≤ 2 X Yields $184,000 1 Coils 1 2 3 4 Bands 8 Further Nodes 3 Upper Branch Coils ≥ 2 2 X Yields $160,000 1 Node 4: Lower Branch Coils ≤ 1 Coils 1 2 3 4 Bands 9 Further Nodes 3 X Yields $177,143 2 Node 5: Upper Branch Coils ≥ 2 1 Lower Branch Coils ≤ 1 Coils 1 2 3 4 Bands 10 The Best Answer The best answer yields $60,000*2 + $50,000*1= $170,000 3 Node 6: Lower Branch Bands ≤ 1 2 X Yields $170,000 1 Coils 1 2 3 4 Bands 11 Rounding Fails 3 IP Solution Coils Limit 2 X Production Capacity LP Solution 1 X Bands Limit Coils 1 2 3 4 Bands 12 Branch & Bound Implicit enumeration An Integer Program with 30 binary variables can require over 1 billion nodes! Comes with guarantees The answer is no worse than… And no better than… Typically finds a good answer quickly Spends a long time guaranteeing it 13 A Solver Model Steel Cable Company Integer Programming Example Products Hours/Ton Profit/Ton Production Plan Products Tons Produced Bands Coils 3 4 $ 50,000 $ 60,000 Bands Maximum Sales Coils 0 0 3 2 Production Constraint Hours Used 0 <= Profit Summary Bands $ - Coils $ - Hours Available 12 Total $ - 14 Integer Variables Integer: -2, -1, 0, 1, 2, … Binary: 0 or 1 Binary: Yes or No, On or Off 15 Single Sourcing Assign each customer to only one DC Simplifies service network 16 Dealers sourced multiple 17 New Ramp Allocation Southern US Dealers sourced by single ramps 18 Lower Cost? Does Single-Sourcing Reduce/Increase distribution cost? 19 Modeling Single-Sourcing Vanilla Approach set DCS; set CUSTOMERS; param Capacity{DCS}; param Demand{CUSTOMERS}; param Cost{DCS, CUSTOMERS}; var Assign{DCS, CUSTOMERS} binary; minimize TotalCost: sum{dc in DCS, cust in CUSTOMERS} Cost[dc, cust]*Assign[dc, cust] + Other Costs 20 DC gets all the Demand s.t. SingleSource{cust in CUSTOMERS}: sum{dc in DCS} Assign[dc, cust] = 1; s.t. ObserveCapacity{dc in DCS}: sum{cust in CUSTOMERS} Demand[cust]*Assign[dc,cust] <= Capacity[dc]; 21 Or Part of a Larger Model s.t. MeetDemand{dc in DCS}: sum of flows into the dc = sum{cust in CUSTOMERS} Demand[cust]*Assign[dc,cust]; 22 What’s the Problem? Size! Thousands of customers Scores of DCs Hundreds of thousands of Integer Variables Most useless! Assign a Customer in ME to a DC in CA? 23 Practical Solution Don’t naively include all possible assignments Only include those: Within a specified distance Among the N closest …. 24 Fixed Costs Revisited Steco's Warehouse Location Model Unit Costs Warehouse A B C Lease Unit Cost/Truck to Sales District 2 3 4 ($) 1 $ 7,750 $ 170 $ 40 $ 70 $ 160 $ 4,000 $ 150 $ 195 $ 100 $ 10 $ 5,500 $ 100 $ 240 $ 140 $ 60 Monthly Trucks From/To Decisions Yes/No Lease A 0 Lease B 0 Lease C 0 Total TrucksTo Demand (Trucks/Mo) A B C Totals Lease Cost $ $ $ $ - 1 0 0 0 0 100 To 1 $$$$- 2 0 0 0 0 90 To 2 $$$$- 3 0 0 0 0 110 To 3 $$$ 0 $ 0 4 0 0 0 0 60 Total 0 0 0 Truck To 4 $ $$ $ (0) $ (0) $$ 0 $ (0) $ 0 Eff. Cap. 0 0 0 Cap. 200 250 300 Total Cost $ $ (0) $ 0 $ 0 25 Binary Switches Variables Yes/No: Lease warehouse or not (Binary) Shipments from Warehouses to Sales Districts Constraints: Meet Demand Don’t exceed Leased Capacity Yes/No leased Warehouse *Capacity of Warehouse At Warehouse B: Effective Capacity = 0*250 At Warehouse A: Effective Capacity = 1*200 Yes/No must be binary 26 Objective Variable Cost for Trucks $100/truck from Warehouse C to District 1 “Fixed” Costs for Leasing $5,500 if we lease Warehouse C $5,500*Yes/No Lease Warehouse C Careful about combining operational costs and capital costs 27 An AMPL Model set WAREHOUSES; param Capacity{WAREHOUSES}; param Lease{WAREHOUSES}; set DISTRICTS; param Demand{DISTRICTS}; param TruckCost{WAREHOUSES, DISTRICTS}; 28 var Open{WAREHOUSES} binary; var Ship{WAREHOUSES, DISTRICTS} >= 0; minimize TotalCost: sum{w in WAREHOUSES} Lease[w]*Open[w] + sum{w in WAREHOUSES, d in DISTRICTS} TruckCost[w,d]*Ship[w,d]; s.t. MeetDemand{d in DISTRICTS}: sum{w in WAREHOUSES} Ship[w,d] >= Demand[d]; s.t. ObserveEffectiveCapacity{w in WAREHOUSES}: sum{d in DISTRICTS} Ship[w,d] <= Capacity[w]*Open[w]; 29 Challenge: Challenge 2 Revisited At least 5 funds At most 10 funds At least 10% if any Fund Ratings Fund Name Fidelity Adv Equity Fidelity Advisor Gro Fidelity Equity-Income Fidelity Equity Income-II Fidelity Growth/Income Fidelity Ins Cash Po Fidelity Investment Fidelity Intermediat Fidelity Limited Ter Fidelity Mortgage Se Fidelity Retirement Fidelity Short-Term Fidelity Value Fund Fidelity Worldwide F Totals 0.00 0.00 0.00 0.00 0.00 0.43 0.16 0.00 0.00 0.00 0.25 0.00 0.00 0.16 1.00 Targets Excess ShortFall Adjusted Deviation 29.29 T-Bill 7 0 0 0 2 100 0 13 5 53 0 44 0 0 43.00 Large Value 71 48 60 66 47 0 0 0 18 0 8 0 50 27 6.24 Large Growth 2 5 5 4 0 0 0 0 0 0 35 0 5 0 8.75 Small Value 6 26 20 16 17 0 2 0 0 0 24 0 31 14 8.52 Small Growth 7 7 0 0 11 0 0 0 0 0 16 0 1 0 4.00 Japan 2 0 3 2 3 0 0 0 0 2 1 0 4 11 1.98 Pacific 0 0 0 1 0 0 0 0 4 1 0 0 0 0 - Europe 0 11 0 0 5 0 0 0 0 3 3 0 8 37 6.56 Emerging Markets 5 2 3 6 2 0 4 0 0 0 11 6 2 11 5.13 Government 0 0 0 0 0 0 92 83 45 34 0 25 0 0 15.00 43 43.00 - 3 3.24 3.00 3.24 3 5.75 3.00 5.75 5 3.52 5.00 3.52 4 4.00 - 10 8.02 10.00 8.02 2 2.00 2.00 2.00 5 1.56 5.00 1.56 10 4.87 10.00 4.87 15 15.00 - High Yield 0 0 9 5 12 0 1 0 28 7 0 23 0 0 0.16 0 0.16 (0.00) 0.16 International Bonds 0 0 0 0 0 0 0 3 0 0 0 3 0 0 0 0.00 (0.00) 0.00 Summary var Invest{FUNDS} binary; var Fraction{FUNDS} >= 0; s.t. MaxHoldings; sum{f in FUNDS} Invest[f] <= 10; s.t. MinHoldings; sum{f in FUNDS} Invest[f] >= 5; s.t. MinimumPercentage{f in FUNDS}: Fraction[f] >= 0.10*Invest[f]; ... 31 Don’t Forget S.t. DefineInvest{f in FUNDS}: Invest[f] >= Fraction[f]; Can’t put money in fund unless you admit to being invested in it. 32 Set Covering Models 33 WesternAir Western Airlines Hub Selection Mile 1000 Distance Matrix AT BO AT 1,037 BO 1,037 CH 674 1,005 DE 1,398 1,949 HO 789 1,804 LA 2,182 2,979 NO 479 1,507 NY 841 222 PI 687 574 SL 1,878 2,343 SF 2,496 3,095 SE 2,618 2,976 CH 674 1,005 1,008 1,067 2,054 912 802 452 1,390 2,142 2,013 DE 1,398 1,949 1,008 1,019 1,059 1,273 1,771 1,411 504 1,235 1,307 HO 789 1,804 1,067 1,019 1,538 356 1,608 1,313 1,438 1,912 2,274 LA 2,182 2,979 2,054 1,059 1,538 1,883 2,786 2,426 715 379 1,113 NO 479 1,507 912 1,273 356 1,883 1,311 1,070 1,738 2,249 2,574 NY 841 222 802 1,771 1,608 2,786 1,311 368 2,182 2,934 2,815 PI 687 574 452 1,411 1,313 2,426 1,070 368 1,826 2,578 2,465 SL 1,878 2,343 1,390 504 1,438 715 1,738 2,182 1,826 752 836 SF 2,496 3,095 2,142 1,235 1,912 379 2,249 2,934 2,578 752 808 SE 2,618 2,976 2,013 1,307 2,274 1,113 2,574 2,815 2,465 836 808 - 34 Summary Mixed Integer Programming Models Mostly about Binary Variables (Logic) Significantly Harder to solve Significantly More Modeling Power Fixed Costs If-Then Constraints Cardinality Constraints Set Covering Models …. 35