Report

WOOD 492 MODELLING FOR DECISION SUPPORT Lecture 17 Integer Programming Integer Programming (IP) • For discrete inputs/outputs – Number of workers required in a factory • For binary variables (yes/no decisions) – Building a facility • For logical conditions (if {x} then {y}) – If sawing pattern 1 is selected, then sawing pattern 2 can not be selected Oct 17, 2012 Wood 492 - Saba Vahid 2 Example 9: Integer Formulation Example • A facility location problem – A manufacturing company has $10 million available capital and would like to invest this in building new factories and warehouses in Los Angeles and San Francisco in order to maximize Net Present Value (NPV). – Decision Variables: which facilities to build? (either build or don’t build, binary) – Constraints: – Factories can be built in L.A. or S.F, or both – Only one warehouse can be located and should be in a city where a new factory is being built Oct 17, 2012 Yes/No Variable NPV Capital required Factory in L.A. X1 $9 m $6 m Factory in S.F X2 $5 m $3 m Warehouse in L.A. X3 $6 m $5 m Warehouse in S.F. X4 $4 m $2 m Wood 492 - Saba Vahid 3 • This is a Binary Integer Program (BIP) • Obj Z=9 X1 +5 X2 +6 X3 +4 X4 (Total NPV) • Subject to: 6 X1+3 X2+ 5 X3+ 2 X4 X3+ -X1 X4 + X3 - X2 + X4 Xi Xi 10 (Total Capital) 1 (One warehouse) 0 (warehouse and factory 0 in the same city) 1 (Upper bound) 0 (Lower Bound) LP Matrix Oct 17, 2012 Wood 492 - Saba Vahid 4 Using indicator variables • Indicators are binary variables used for modelling problems with: – – – – Fixed costs Either/OR constraints If/Then constraints … Oct 17, 2012 Wood 492 - Saba Vahid 5 Fixed-Charge Problems • When taking up an activity has a one-time fixed cost – production line set-up cost – Road establishment cost • Example: – A cabinet manufacturer can outsource the cabinet doors at $20/door or make them in the factory with $500 line set-up cost and then $10/door production cost. Oct 17, 2012 Wood 492 - Saba Vahid 6 Fixed-Charge Problems • Objective is to minimize costs • Decision variables are – X1 number of outsourced doors – X2 number of manufactured doors • Total cost for outsourced doors: • 20 X1 • Total cost for the manufactured doors: • 0 • 500 + 10 X2 Oct 17, 2012 if X2=0 if X2>0 Wood 492 - Saba Vahid 7 Fixed-Charge Problems • How can we force the $500 costs when X2 is greater than 0? • We define an indicator variable Y2 : – if X2=0 then Y2=0 – otherwise Y2=1 – Now, rewrite the formula for production cost: • Manufacturing cost: 500 Y2 + 10 X2 • Objective: Min Z= 20 X1 + 500 Y2 + 10 X2 Oct 17, 2012 Wood 492 - Saba Vahid 8 Fixed-Charge Problems • Now, how to ensure that Y2 value changes according to X2 value? • Big M method: – Choose a big number M (relative to problem parameters, bigger than any possible value of X2) – Add the following to the existing constraints • X2 <= M.Y2 • Y2 is binary – How does this constraint work? • If X2>0, then Y2 has to be 1, so that X2<=M • If X2=0, then Y2 can be either 0 or 1, however since 500Y2 is a term in the objective function, the solution algorithm always picks Y2=0, because it results in the lower objective function value Oct 17, 2012 Wood 492 - Saba Vahid 9 Either/OR Constraints • When only one of two constraints must hold – E.g. there are two suppliers for cabinet doors – Each supplier has a certain number of doors available for shipping – Only one of the suppliers can be selected • Variables: number of doors purchased (X) • Supply constraints (depending on which supplier is elected): – Either X <= 100 – OR X <= 150 Oct 17, 2012 Wood 492 - Saba Vahid 10 Either/OR Constraints • Define an indicator variable Y: – If first supplier is selected, Y=1 and first constraint is activated – otherwise Y=0 and second constraint is activated • Use the Big M Method – Constraint 1: X <= 100 + M. (1-Y) – Constraint 2: X <= 150 + M. Y • How does this formulation work? – If supplier 1 is selected, then Y=1, so the first constraint will be X<=100 and the second constraint will be X<=150+M which in effect eliminates the second constraint (since M is a really big number) – If supplier 2 is selected, then Y=0 and the first constraint is eliminated – The solution algorithm picks the Y value that results in the best value of the objective function Oct 17, 2012 Wood 492 - Saba Vahid 11 Lab 6 preview • Same problem as in Lab 3 • Adding extra constraints: – Building the roads to each cut block (if we harvest, we have to build the road first) – Selecting only one sawing pattern for all log sizes – Selecting the optimal number of shifts to run the sawmill (1,2, or 3) LP matrix Oct 17, 2012 Wood 492 - Saba Vahid 12 Next Class • Branch and bound Oct 17, 2012 Wood 492 - Saba Vahid 13