Integer Programming Models

Introduction to Integer Programming Integer programming models 1 A 2-Variable Integer program maximize 3x + 4y subject to 5x + 8y ≤ 24 x, y ≥ 0 and integer What is the optimal solution? 2 The Feasible Region 5 Question: What is the optimal integer solution? 2 3 4 What is the optimal linear solution? 0 1 Can one use linear programming to solve the integer program? 0 1 2 3 4 5 A rounding technique that sometimes is useful, and sometimes not. 2 Optimal is x=3, y=1, and z =13 0 Same solution value at x=0, y=3. 1 3 4 5 Solve LP (ignore integrality) get x=24/5, y=0 and z =14 2/5. Round, get x=5, y=0, infeasible! Truncate, get x=4, y=0, and z =12 0 1 2 3 4 5 Why integer programs? Advantages of restricting variables to take on integer values – More realistic – More flexibility Disadvantages – More difficult to model – Can be much more difficult to solve 5 On 0-1 variables Integer programs: linear equalities and inequalities plus constraints that say a variable must be integer valued. We also permit “xj ∈{0,1}.” This is equivalent to 0 ≤ xj ≤ 1 and xj integer. 6 The mystery of integer programming Some integer programs are easy (we can solve problems with millions of variables) Some integer programs are hard (even 100 variables can be challenging) It takes expertise and experience to know which is which 7 Types of integer programs All integer programs have linear equalities and inequalities and some or all of the variables are required to be integer. A Pure Integer Program: all variables are required to be integral. Max 6x1+ 2x2+ 2x3+ 8x4 5x1+ 3x2+ 4x3+ 3x4 ≤ 25 x1+ x2+ x3+ x4 ≤ 8 xj ≥ 0 and integer for each j = 1 to 4 8 Binary (or 0-1) Integer Program: all variables are required to be 0 or 1 Max 8x1+ 4x2+ 2x3+ 3x4 5x1+ 3x2+ 4x3+ 3x4 ≤ 10 x1+ x2+ x3+ x4 ≤ 3 xj ∈ {0,1} for each j = 1 to 4 Recall: the constraint xj ∈ {0,1} is equivalent to 0 ≤ xj ≤ 1 and xj is integer 9 Mixed Linear Integer Program (MILP) Some but not necessarily all variables are required to be integer. Other variables are permitted to be fractional. Max 6x1+ 2x2+ 2x3+ 4y 5x1+ 3x2+ 4x3+ 3y ≤ 25 x1+ x2+ x3+ y ≤ 8 xj ≥ 0 and integer for each j = 1 to 3 y≥0 10 Objective for the rest of this lecture: introduce modeling in integer programming Formulate some classic integer programs – Capital budgeting / knapsack – Covering Problems Show techniques for transforming into integer programs – Transforming logical constraints – Transforming fixed charge non-linear functions 11 Stockco Example: a binary IP Stockco is considering 6 investments. The cash required from each investment as well as the NPV of the investment is given next. The cash available for the investments is $14,000. Stockco wants to maximize its NPV. What is the optimal strategy? An investment can be selected or not. One cannot select a fraction of an investment. 12 Data for the Stockco Problem Investment budget = $14,000 Investment 1 2 3 4 5 6 Cash Required (1000s) $5 $7 $4 $3 $4 $6 $22 $12 $8 $11 $19 NPV added (1000s) $16 13 Integer Programming Formulation What are the decision variables? ⎧ 1, if we invest in i = 1,...,6, xi = ⎨ ⎩0, otherwise Objective and Constraints? Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6 5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 ≤ 14 xj ∈ {0,1} for each j = 1 to 6 14 Capital Budgeting / Knapsack You have n items to choose from to put into your knapsack. Item i has weight wi, and it has value ci. The maximum weight your knapsack (or you) can hold is b. Formulate the knapsack problem. 15 Models as transformations There is an instance of “Your Problem” and “The IP model” that you create. – For every solution x of your problem, there is a corresponding solution x’ of the IP model with the same cost – For every (optimal) solution y of the IP model, there is a solution y’ of your problem with the same cost. 16 Model as transformations optimum solution x z ≤ z’ x’ Original Problem y Integer Program z ≥ z’ y’ optimum solution Let z be the optimum cost for the original problem (with maximization), and let z’ be the cost for the IP. 17 Illustration: Consider the Stockco Problem with additional constraint: – If stock 1 is selected, then stock 3 is not selected. Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6 5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 ≤ 14 x1 + x3 ≤ 0 xj ∈ {0,1} for each j = 1 to 6 18 If stock 1 is selected, then stock 3 is not selected. Feasible solutions to logical constraint: x1 = 1, x3 = 0 x3 x1 = 0, x3 = 1 x1 = 0, x3 = 0 x1 + x3 ≤ 1 x1 Feasible solutions to integer programming constraint: x1 = 1, x3 = 0 The two models x1 = 0, x3 = 1 are identical. x1 = 0, x3 = 0 19 Transforming either or constraints The constraints of the original problem Either 2x1 + x2 ≤ 5 or 2x3 – x4 ≤ 2 or both 0 ≤ xj ≤ 5 for all j plus other constraints The Integer Program 2x1 + x2 ≤ 5 + 15y1 2x3 – x4 ≤ 2 + 15(1- y1) y1 ∈ {0, 1} 0 ≤ xj ≤ 5 for all j plus other constraints 20 Why the transformation works: Suppose that x, y is feasible for the MILP Either 2x1 + x2 ≤ 5 or 2x3 – x4 ≤ 2 or both 0 ≤ xj ≤ 5 for all j plus other constraints 2x1 + x2 ≤ 5 + 15y1 2x3 – x4 ≤ 2 + 15(1- y1) y1 ∈ {0, 1} 0 ≤ xj ≤ 5 for all j plus other constraints Assume that x, y is a feasible solution for the MILP if y1 = 1, then 2x3 – x4 ≤ 2 and x1, x2, x3, x4, x5 is feasible for the original problem if y1 = 0, then 2x1 + x2 ≤ 5 and x1, x2, x3, x4, x5 is feasible for the original problem 21 Why the transformation works: Suppose that x is feasible for the original problem. Either 2x1 + x2 ≤ 5 or 2x3 – x4 ≤ 2 or both 0 ≤ xj ≤ 5 for all j plus other constraints Assume that x is a feasible solution for the original problem if 2x1 + x2 ≤ 5 then let y1 = 0. Then 2x1 + x2 ≤ 5 + 15y1 = 5 and 2x3 – x4 ≤ 2 + 15(1- y1) = 17 because 0 ≤ xj ≤ 5 for j = 3, 4. So, x1, x2, x3, x4, x5, y1 is feasible for the IP and it will have the same cost as x. 2x1 + x2 ≤ 5 + 15y1 2x3 – x4 ≤ 2 + 15(1- y1) y1 ∈ {0, 1} 0 ≤ xj ≤ 5 for all j plus other constraints if 2x3 + x4 ≤ 2 then let y1 = 1. Then 2x1 + x2 ≤ 5 + 15y1 = 20 because 0 ≤ xj ≤ 5 for j = 3, 4. and 2x3 – x4 ≤ 2 + 15(1- y1) = 2 So, x1, x2, x3, x4, x5, y1 is feasible for the IP, and it will have the same cost as x. 22 Exercise to do with your partner Transform the following into integer linear constraints. 4x1 + 5x2 – 2x3 ≤ 20 or -2x1 - 5x2 + 5x3 ≤ 9 0 ≤ xj ≤ 10 plus other constraints. 23 The game of fiver. Click on a circle, and flip its color and that of adjacent colors. Can you make all of the circles red? 24 The game of fiver. Click on (3, 3) 25 The game of fiver. Click on (1, 1) Click on (5, 5) 26 The game of fiver. Next: an optimization problem whose solution solves the problem in the fewest moves. 27 On forming Integer programs 1. First select the set of decision variables. It turns out that timing does not matter in this game. All that matters is what square are clicked on. 2. Write the objective. 3. Write the constraints. If it is easier to express it using non-linear constraints, or logical constraints, then do this first. 28 Optimizing the game of fiver. 1 1 2 2 3 4 5 Let x(i,j) = 1 if I click on the square in row i and column j. x(i,j) = 0 otherwise. 4 Focus on the element in row 3, and column 2. To turn it red, we require that 5 x(2,2) + x(3,1) + x(3,2) + x(3,3) + x(4,2) is odd 3 29 Optimizing the game of fiver Minimize Σi,j=1 to 5 x(i, j) s.t. x(i, j) + x(i, j-1) + x(i, j+1) + x(i-1, j) + x(i+1, j) is odd for all i, j = 1 to 5. x(i, j) is 0 or 1 for all i, j = 1 to 5. x(i, j) = 0 otherwise. This (with a little modification) is an integer program. 30 Optimizing the game of fiver Minimize Σi,j=1 to 5 x(i, j) s.t. x(i, j) + x(i, j-1) + x(i, j+1) + x(i-1, j) + x(i+1, j) - 2 y(i, j) = 1 for all i, j = 1 to 5. x(i, j) is 0 or 1 for all i, j = 1 to 5. x(i, j) = 0 otherwise 0 ≤ y(i, j) ≤ 2; y(i, j) integer for i, j = 1 to 5. This is an integer program. 31 Should I give away the solution? 32 Fire Station Problem 1 2 5 Locate fire stations so that each district has a fire station in it, or next to it. 3 6 7 4 8 11 9 12 13 10 14 15 16 Minimize the number of fire stations needed. Here is a nonoptimal solution with five fire stations. 33 Representation as Set Covering Problem 1 2 5 3 6 4 8 11 10 14 7 9 12 15 Set # Set 1 {1, 2, 4, 5} 2 {1, 2, 3, 5, 6} 3 {2, 3, 6, 7} 16 {13, 15, 16} 13 16 34 Representation as an integer program Decision variables: •which districts to choose •which sets to choose Constraints Set # Set 1 {1, 2, 4, 5} 2 {1, 2, 3, 5, 6} 3 {2, 3, 6, 7} 16 {13, 15, 16} •each district has a fire station or is next to one •each element gets covered 35 Representation as an integer program xj = 1 if set j is selected xj = 0 otherwise Set # Set Minimize x1 + x2 + … + x16 1 {1, 2, 4, 5} s.t. x1 + x2 + x4 + x5 ≥ 1 2 {1, 2, 3, 5, 6} x1 + x2 + x3 + x5 + x6 ≥ 1 3 {2, 3, 6, 7} 16 {13, 15, 16} x13 + x15 + x16 ≥ 1 xj ∈ {0, 1} for each j. 36 On Covering Problems “Covering Problems” model a number of applied situations. – Assigning pilots and stewards to planes – Assigning police cars, ambulances, and other city personnel – package delivery, oil delivery, etc. 37 Fixed Charge Problems. Lowell Cloth example (from IMP) Shirts Labor 3 Cloth (yds) 4 Profit $6 Shorts 2 3 $4 Pants Supply 6 150 4 160 $7 Lowell Cloth wants to produce shirts, shorts, and pants for the week to maximize their profit. However, to make shirts or shorts or pants, they need to rent a machine. machine rental cost Shirts $200 Shorts $150 Pants $100 38 Formulation as a non-linear program (NLP) x1 = Number of shirts made f1(0) = f2(0) = f3(0) = 0 x2 = Number of shorts made f1(x1) = 6x1 – 200 for x1 > 0 x3 = Number of pants made f2(x2) = 4x2 – 150 for x2 > 0 f3(x3) = 7x3 – 100 for x3 > 0 Max f1(x1) + f2(x2) + f2(x3) s.t. 3x1 + 2x2 + 6x3 ≤ 150 (labor) 4x1 + 3x2 + 4x3 ≤ 160 (cloth) x1, x2, x3 ≥ 0 39 Transformation to an MILP x1 = Number of shirts made Let yj = 0 if xj = 0 x2 = Number of shorts made Let yj = 1 if xj > 0 x3 = Number of pants made yj : fixed charge variable Max 6x1 + 4x2 + 7x3 - 200 y1 – 150 y2 – 100 y3 s.t. 3x1 + 2x2 + 6x3 ≤ 150 (labor) 4x1 + 3x2 + 4x3 ≤ 160 (cloth) x1, x2, x3 ≥ 0 + constraints involving y Note: xj ≤ 60 for all j in any feasible solution 40 Transformation to an MILP Max 6x1 + 4x2 + 7x3 - 200 y1 – 150 y2 – 100 y3 s.t. 3x1 + 2x2 + 6x3 ≤ 150 (labor) 4x1 + 3x2 + 4x3 ≤ 160 (cloth) xj ≤ 60 yj for j = 1, 2, 3 y1, y2, y3 ∈ {0, 1}, x1, x2, x3 ≥ 0 Why this transformation is valid (Part 1): Suppose that x is feasible for the original problem. Then x, y is feasible for the MILP, where yj = 0 if xj = 0 and yj = 1 if xj > 0. And x, y has the same profit as x does in the NLP 41 Transformation to an MILP Max 6x1 + 4x2 + 7x3 - 200 y1 – 150 y2 – 100 y3 s.t. 3x1 + 2x2 + 6x3 ≤ 150 (labor) 4x1 + 3x2 + 4x3 ≤ 160 (cloth) xj ≤ 60 yj for j = 1, 2, 3 y1, y2, y3 ∈ {0, 1}, x1, x2, x3 ≥ 0 Why this transformation is valid (Part 2): Suppose that x, y is optimal for the MILP. If xj = 0, then yj = 0 for j = 1 to 3. Otherwise, x, y is not optimal. Then x is feasible for the NLP, and it has the same profit as does x, y for the MILP. 42 Using Excel Solver to Solve Integer Programs Add the integrality constraints (or add that a variable is binary) Set the Solver Tolerance. (The tolerance is the percentage deviation from optimality allowed by solver in solving Integer Programs.) – The default is 5% – The default is way too high – It often finds the optimum for small problems 43 Some Comments on IP models There are often multiple ways of modeling the same integer program. Solvers for integer programs are extremely sensitive to the formulation. (not true for LPs) 44 Example constraint A: 2x1 + 2x2 + … + 2x50 ≤ 51 constraint B: x1 + x2 + … + x50 ≤ 25 – assume that x is binary constraints C: x1 ≤ y, x2 ≤ y, …, x50 ≤ y (where y is binary) constraint D: x1 + … + x50 ≤ 50 y B is a better formulation than A, C is better than D It is not obvious why, until you see the algorithms. 45 Summary on Integer Programming Dramatically improves the modeling capability – Economic indivisibilities – Logical constraints – Modeling fixed charges – classical problems in capital budgeting and location Not as easy to model Not as easy to solve. 46 The following slides are not part of the class notes. They were additional slides used in previous years. 47 The number of stocks selected is not three Either x1+x2+x3+x4+x5+x6 ≥ 4 or (1) x1+x2+x3+x4+x5+x6 ≤ 2 (2) an auxiliary variable w ∈ {0,1} with the following properties: Add If w = 1, then the first constraint is satisfied (A) If w = 0, then the second constraint is satisfied (B) Since w is 0 or 1, at least one of the two constraints must be satisfied. 48 The number of stocks selected is not three (cont’d) Add the constraint: x1+x2+x3+x4+x5+x6 ≥ 4w So, if w=1 then x1+x2+x3+x4+x5+x6 ≥ 4 (A) (1) Note: if w = 0, the first constraint is automatically satisfied. So, if w=0 then x1+x2+x3+x4+x5+x6 ≤ 2 + 4w (B) x1+x2+x3+x4+x5+x6 ≤ 2 (2) Note: if w = 1, the second constraint is automatically satisfied. (If we had written “≤ 2 + 3w”, then we would incorrectly have eliminate the solution in which xj = 1 for all j.) 49 You must select stock 1 unless the NPV of the portfolio exceeds $42,000. If NPV < 42 then x1=1. Add the constraint: x1 ≥ (42 – NPV)/42. A larger denominator will also work. Recall that NPV is 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6 42x1 ≥ 42 - (16x1+22x2+12x3+8x4+11x5+19x6) 50 Possible constraints in integer programs The previous constraints represent “economic indivisibilities”, either a project is selected, or it is not. There is no selecting of a fraction of a project. Similarly, integer variables can model logical requirements (e.g., if stock 2 is selected, then so is stock 1.) 51 How to model “logical” constraints Exactly 3 stocks are selected. If stock 2 is selected, then so is stock 1. If stock 1 is selected, then stock 3 is not selected. Either stock 4 is selected or stock 5 is selected, but not both. Ask persons to spend 5 minutes modeling as many of these constraints as possible. The goal is to model constraints, so do not pay any attention to what the optimal solution is. After they have had 5 minutes let’s do this on the board. 52 Formulating Constraints Exactly 3 stocks are selected x1+ x2+ x3+ x4+ x5+ x6=3 Sum (xi) = 3 53 If stock 2 is selected then so is stock 1 The integer programming constraint: A 2-dimensional representation x1 ≥ x2 Stock 2 Stock 1 Work with your partner for 5 minutes trying to model the other constraints. 54 If stock 1 is selected then stock 3 is not selected The integer programming constraint: A 2-dimensional representation x1 + x3 ≤ 1 Stock 3 Stock 1 55 Either stock 4 is selected or stock 5 is selected, but not both. The integer programming constraint: A 2-dimensional representation x4 + x5 = 1 stock 5 stock 4 56 Representing Non-linear functions Suppose that the cost of computers is as follows: – $2,000 each if you buy 1 to 10 – $1,800 for each computer from 11 to 25 – $1,700 for each computer from 26 to 50 – No more than 50 may be purchased. – Let x = number of computers bought – x1 = number bought at $2,000 – x2 = number bought at $1,800 – x3 = number bought at $1,700 s.t. 0 ≤ x1 ≤ 10 0 ≤ x2 ≤ 15 0 ≤ x3 ≤ 25 If x1 < 10, then x2 = 0. If x2 < 15, then x3 = 0. Minimize 2,000 x1 +1,800 x2 + 1,700 x3 57 Representing Non-linear functions Minimize 2,000 x1 +1,800 x2 + 1,700 x3 s.t. 0 ≤ x1 ≤ 10 0 ≤ x2 ≤ 15 w1 0 ≤ x3 ≤ 25 w2 If x < 10, then x2 = 0. 0 ≤ 1w1 ≤ x1/10 If x < 15, then x3 = 0. 0 ≤ 2w2 ≤ x2/15 Let w1 = 1 if x1 = 10 w1 = 0 if x1 < 10 Let w2 = 1 if x2 = 15 w2 = 0 if x2 < 15 w1, w2 ∈ {0, 1} If x1 < 10, then x2 = 0. If w1 = 0, then x2 = 0. If x2 < 15, then x3 = 0. If w2 = 0, then x3 = 0. 58 Is this formulation correct? It models the x’s correctly. It does not model the w’s perfectly. – Suppose x1 = 10, x2 = x3 = 0; – Then w1 = 0 or 1 – Cost = 20,000, regardless. 59 Warehouse location problem skip n warehouses – cost fj of opening warehouse j m customers – customer i has a “demand” of di – unit shipping cost cij of serving customer i via warehouse j. Variables: – let yj = 1 if warehouse j is opened – Let xij = amount of demand for customer i satisfied via warehouse j. 60 Suppose you knew which warehouses were open. S = set of open warehouses xij = demand satisfied for customer i at warehouse j yj = 1 for j in S, yj = 0 for j not in S. subject to: customers get their demand satisfied no shipments are made from an empty warehouse Σi,j cijxij + Σj∈S fj minimize Σj xij = di xij ≤ di xij = 0 if yj = 1 if yj = 0 and x ≥ 0 61 More on warehouse location yj = 1 if warehouse i is opened yj = 0 otherwise xij = flow from i to j Σi,j cijxij + Σj fi yi minimize subject to: customers get their demand satisfied each warehouse is either opened or it is not (no partial openings) no shipments are made from an empty warehouse Σi xij = dj 0 ≤ yj ≤ 1 yj integral for all j. xij ≤ dj yi for all i, j and x ≥ 0 62 Two key aspects of using integrality in the model Costs: we include the cost of the warehouse only if it is opened. Σi fi yi Constraints: We do not allow shipping from warehouse j if it is not opened. – xij ≤ dj yi for all i, j 63 More on warehouse location The above is a core subproblem occurring in supply chain management, and it can be enriched – more complex distribution system – capacity constraints – non-linear transportation costs – delivery times – multiple products – business rules – and more 64 The IP Either 2x1 + x2 ≤ 5 or 2x3 – x4 ≤ 2 or both. 2x1 + x2 ≤ 5 + 15y1 2x3 – x4 ≤ 2 + 15(1- y1) y1 ∈ {0, 1}. In Case 1, 2x1 + x2 ≤ 5 3 0 1 2 2 x4 0 1 x2 3 4 4 5 5 Case 1. y1 = 0 0 1 2 x1 3 4 5 0 1 2 x3 3 4 5 65 The IP Either 2x1 + x2 ≤ 5 or 2x3 – x4 ≤ 2 or both. 2x1 + x2 ≤ 5 + 15y1 2x3 – x4 ≤ 2 + 15(1- y1) y1 ∈ {0, 1}. In Case 2, 2x3 – x4 ≤ 2. 3 0 1 2 2 x4 0 1 x2 3 4 4 5 5 Case 2. y1 = 1 0 1 2 x1 3 4 5 0 1 2 x3 3 4 5 66 Representation as a graph problem Replace each district with a node. Two nodes are adjacent if their districts are adjacent A node covers itself and its neighbors. Thus, node 16 covers nodes 13, 15, 16. What is the minimum size of a subset of nodes that covers all of the nodes? 67 The Graph Cover Problem 1 2 5 3 6 4 8 11 10 14 7 9 12 15 Set # Set 1 {1, 2, 4, 5} 2 {1, 2, 3, 5, 6} 3 {2, 3, 6, 7} 16 {13, 15, 16} 13 16 68