Optimization Methods in Management Science Introduction to Integer Programming

z Introduction to Integer Programming Integer programming models Quotes of the Day Somebody who thinks logically is a nice contrast to the real world. -- The Law of Thumb “Take some more tea,” the March Hare said to Alice, very earnestly. “I’ve had nothing yet,” Alice replied in an offended tone, “so I can’t take more.” “You mean you can’t take less,” said the Hatter. “It’s very easy to take more than nothing.” -- Lewis Carroll in Alice in Wonderland Integer Programs Integer programs: a linear program plus the additional constraints that some or all of the variables must be integer valued. We also permit “xj ∈{0,1},” or equivalently, “xj is binary” This is a shortcut for writing the constraints: 0 ≤ xj ≤ 1 and xj integer. Integer programs are limited in form in that they can only include: 1. a linear objective 2. linear inequalities and equalities 3. Some or all of the variables can be required to be integer valued. 4. Since it is so easy to model that xj ∈ {0, 1}, we permit this type of constraint as well. A 2-Variable Integer program maximize 3x + 4y subject to 5x + 8y ≤ 24 x, y ≥ 0 and integer z What is the optimal solution? Integer programs are notoriously hard to solve. We illustrate this by pointing out that even a relatively simple integer program offers some challenges. The Feasible Region 5 Question: What is the optimal integer solution? 3 4 What is the optimal linear solution? 0 1 2 Can one use linear programming to solve the integer program? 0 1 2 3 4 5 The feasible region here consists of the yellow circles only. A rounding technique that sometimes is useful, and sometimes not. 0 1 2 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 Same solution value at x=0, y=3. Optimal is x=3, y=1, and z =13 0 1 2 3 4 5 Often we will consider the “linear programming relaxation” of an integer program. This relaxation is obtained by dropping the integrality constraints. In this case, if we solve the linear programming relaxation, we get the solution x = 24/5, y = 0. It’s somewhat close to the optimal integer solution. However, in this case, it doesn’t really help us to obtain the optimum integer solution. Why integer programs? z Advantages of restricting variables to take on integer values – More realistic – More flexibility z Disadvantages – More difficult to model – Can be much more difficult to solve In practice, most problems have at least some features that prevent linear programming from being a good enough model. For this reason, integer programming models are much more practical. They can model logical constraints, nonlinear functions, and much more. While it is a robust and excellent modeling tool, it is much harder to solve than linear programs. Trading for Profit Nooz is a contestant on Trading for Profits. Its main slogan is “I ♥ Trading for Profit” Nooz has just won 14 IHTFP points. We now join the quiz show to see what the 14 points are worth. We illustrate integer programming on a contestant choosing prizes in a game show. iPod 5 points gift certificate 3 points server 7 points Tutoring in 6.041 4 points brass rat 4 points 15.053 6 points I got a bit carried away last year in developing these voiceovers. I hope they play on your computer. In any case, the products are 1. An iPod plus speaker 2. A server for holding vast amounts of data 3. A “brass rat” 4. A $500 gift certificate to Au Bon Pan 5. Tutoring in 6.041. 6. Dinner with Professor Orlin and the TAs iPod server brass rat gift certificate 5 points 7 points 4 points 3 points 16 utils 22 utils 12 utils 8 utils 6.041 15.053 4 points 6 points 11 utils 19 utils Nooz determines what each prize is worth to him. He measure everything in “utils” on a scale from 1 to 25. Nooz converts each product into Utils. You may note that each IHTFP point is worth approximately 3 utils, but the actual numbers vary from product to product. Prize iPod 1 server 2 brass rat 3 gift certificate 6.041 15.053 4 5 6 Points 5 7 4 3 4 6 Utility 16 22 12 8 11 19 Budget: 14 IHTFP points. Write Nooz’s problem as an integer program. ⎧1 Let x i = ⎨ ⎩0 if prize i is selected otherwise Nooz’s problem is to maximize the total utility subject to using at most 14 IHTFP points. The first step is choosing decision variables. The rule of thumb in integer programming is as follows: whenever it makes sense at all, try to use binary decision variables. Binary decision variables are great for modeling decisions where one of two choices can be made. As we shall see in the next lecture, they are also useful when one needs to make a decision of one of many choices. In this case, we let xj = 1 or 0 according as prize j is selected or is not selected. Integer Programming Formulation 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 We will solve this problem in two lectures. The objective and constraints show up in slideshow mode. Knapsack or Capital Budgeting z You have n items to choose from to put into your knapsack. z Item i has weight wi, and it has value ci. z The maximum weight your knapsack (or you) can hold is b. z Formulate the knapsack problem. The structure of this problem is as follows: 1. a linear objective 2. a single linear contraint 3. each variable is binary. This problem arises so frequently that it is given a name. The most common name is the knapsack problem, because it can be used to model the following problem: what is the choice of items to put in your knapsack so as to maximize the total value and so that the weight in the knapsack is at most some specified number b? It is often referred to as capital budgeting. In this case, it models the following problem: Given: a budget b, and a number of different projects, where the j-th project requires a budget of wj and gives a net present value return of cj. What is the choice of projects that maximizes the net present revenue without exceeding the budget b? The mystery of integer programming z Some integer programs are easy (we can solve problems with millions of variables) z Some integer programs are hard (even 100 variables can be challenging) z It takes expertise and experience to know which is which z It’s an active area of research at MIT and elsewhere Researchers have been working on integer programming for nearly 50 years, and have tried to develop great solution techniques. But to this day, there are many problems that are easily solved (despite being of rather large size) and other problems that cannot be solved even approximately (despite having far fewer variables). Researchers believe that this is inherent to integer programming models. Some are hard, and some are easy to solve. Researchers in integer programming have put enormous energies into figuring out which problems are easy and which are not. In addition, they have tried to develop increasingly better solution techniques. Types of integer programs z 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 We next point out that there are several varieties of integer programs. Pure integer programs permit integer variables that can take on more values than 0 and 1. These problems are typically very hard to solve. 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 Binary integer programs are typically hard to solve, but easier than pure integer programs. Mixed Linear Integer Program (MILP) z 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 Mixed linear integer programs are typically the hardest problems to solve of all of them. Objective for the rest of this lecture: introduce modeling in integer programming z Logical Constraints z Fixed charge Problems z The Game of Fiver A Standard Approach for IP Formulations Your model in the form of a “word problem” A Math Model sometimes with logical constraints and non-linear functions The transformation to an IP sometimes uses cleverness, sometimes is obvious, and sometimes, you just look up to see how it is done. An Integer Programming Model I strongly urge students to formulate these challenging problems first using any math that is convenient. So, we take a word problem and convert it into a mathematical optimization problem. Subsequently, we convert the mathematical optimization problem into an integer program. server iPod 5 points 16 utils 6.041 4 points 11 utils brass rat 4 points 12 utils 7 points 22 utils gift certificate 3 points 8 utils 15.053 6 points 19 utils Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6 5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 ≤ 14 xj ∈ {0,1} for each j = 1 to 6 Logical Constraints on 0-1 Variables z Consider Nooz’s problem. Suppose he said: – If I select the iPod, then I won’t bother selecting the 6.041 tutoring, since I’ll hope that they podcast the homework solutions. – How would we model this? Max 16x1+ 22x2+ 12x3+ 8x4+ 11x5+ 19x6 5x1+ 7x2+ 4x3+ 3x4+ 4x5+ 6x6 ≤ 14 x1 + x5 ≤ 1 xj ∈ {0,1} for each j = 1 to 6 The constraint x1 + x5 ≤ 1 does not look like the original word problem formulation. But it is equivalent. This is more apparent on the next slide. On logical constraints on binary variables z With logical constraints involving only two variables, one can easily draw the feasible region, and determine what linear constraint is needed. (Actually, lots of different constraints will work). x5 x5 x1 x1 + x5 ≤ 1 2x1 + 2x5 ≤ 3 x1 With only two variables, it is easy to graph the feasible region. In fact, the feasible region consists of 3 points. We want to add a linear constraint that “separates” the infeasible red point from the three feasible black points. There are an infinite number of lines that separates the three feasible points from the infeasible point (1, 1). The simplest and best of these constraints is x1 + x5 ≤ 1. But 2x1 + 2x5 ≤ 3 is also valid. And so is 1000x1 + x5 ≤ 1000, assuming that we also constrain x5 to be 0 or 1. Mental Break Logical Constraints 1 x1 = 1 if iPod x5 = 1 if 6.041 Constraint 1. If you select the iPod, you cannot select 6.041 Feasibility Table x1 x5 Feasible? 0 0 yes 0 1 yes 1 0 yes 1 1 no x5 MIP Constraint: x1 + x5 ≤ 1 x1 Logical Constraints 2 x1 = 1 if iPod x2 = 1 if server Constraint 2. If Prize 1 is selected then Prize 2 must be selected. Feasibility Table x11 x22 Feasible? 0 0 yes 0 1 yes 1 0 no 1 1 yes x2 MIP Constraint: x1 ≤ x2 x1 Once the feasible region is drawn, it is easy to see that there are an infinite number of constraints that separate the three feasible points from the infeasible point (1, 0). The simplest and best of these is x1 ≤ x2 . Logical Constraints 3 x1 = 1 if iPod x2 = 1 if server Constraint 3. You must select Prize 1 or Prize 2 or both Feasibility Table x1 x2 Feasible? 0 0 _________ 0 1 _________ 1 0 _________ 1 1 x2 MIP Constraint: x1 + x2 ≥ 1 x1 The answer is revealed in Slide Show mode. But you may want to figure out the constraint first. Logical Constraints 4 x1 = 1 if iPod x2 = 1 if server Constraint 4. You must select Prize 1 or Prize 2 but not both. Feasibility Table x1 x2 Feasible? 0 0 no 0 1 yes 1 0 yes 1 1 no x2 MIP Constraint: x1 + x2 = 1 x1 This one is a bit trickier since the constraint that separates the feasible points from the infeasible points is an equality constraint. Integer programs and non-linear objectives IPs are great for modeling non-linear objectives z Fixed charge problems – you need to pay an up front price for producing anything. Costs are linear after that. z General non-linear functions of one variable Fixed Charge Problems: z Data for Zor’s problem. Gold Silver Bronze Available TA labor 2 4 5 100 lead 1 1 1 30 pixie dust 10 5 2 204 Profit (Euros) 52 30 20 Cost of set up 500 400 300 Suppose that Zor is unable to get any of his reactions going without an expensive set up. After that there is no additional cost beyond material and labor. Here we consider the problem of Zor trying to optimize the production of gold, silver, and bronze using TA labor, pixie dust, and lead. But we have introduced a new feature called a “fixed charge.” In order to make a product, Zor must set up the production at a fixed cost. For example, to make any gold, Zor needs to pay 500 Euros for the set up. After that, there is no additional cost. Similarly, Zor has a fixed charge for producing silver and bronze. Zor does not have to pay the fixed charge if he doesn’t produce the metal. Zor’s original problem Maximize 52 x1 + 30 x2 + 20 x3 subject to 2 x1 + 4 x2 + 5 x3 1 x 1 + 1 x2 + 1 x 3 ≤ 100 ≤ 30 10 x1 + 5 x2 + 2 x3 ≤ 204 New variables ⎧1 w1 = ⎨ ⎩0 x1 ≥ 1 x1 = 0 ⎧1 w2 = ⎨ ⎩0 x2 ≥ 1 x2 = 0 ⎧1 w3 = ⎨ ⎩0 x3 ≥ 1 x1, x2 , x3 ≥ 0 integer Part of the math model. We need to transform this into an IP model. x3 = 0 In order to model Zor’s problem as an IP, we create three new binary variables. The variable w1 indicates whether Zor produces gold or not. The variables w2 and w3 indicate whether Zor produces silver or bronze. The description of the variables on this slide is a valid mathematical formulation of the variables, but it is not part of the integer program itself. We need to write integer linear constraints that will ensure the variables w are correctly defined. Modeling Fixed Charges Note: x1 ≤ 20 (constraint 3), x2 ≤ 30 (constraint 2) x3 ≤ 20 (constraint 1). We need upper bounds on variables in order to create the IP model. New variables ⎧1 w1 = ⎨ ⎩0 x1 ≥ 1 x1 = 0 x1/20 ≤ w1 ≤ x1 w1 ∈ {0, 1} ⎧1 w2 = ⎨ ⎩0 x2 ≥ 1 x2 = 0 x2/30 ≤ w2 ≤ x2 w2 ∈ {0, 1} ⎧1 w3 = ⎨ ⎩0 x3 ≥ 1 x3/20 ≤ w3 ≤ x3 w3 ∈ {0, 1} x3 = 0 In order to write the constraints of the IP, it turns out that we need to have upper bounds on x1, x2, and x3. This is not obvious yet, but you will see why the upper bounds are needed. We know that x1 is between 0 and 20. We want to force w1 to be 0 whenever x1 is 0. And we want to force w1 to be 1 whenever x1 is between 1 and 20. This is accomplished as x1/20 ≤ w1 ≤ x1 . You can verify that w1 will be defined as we want with these constraints, assuming we also add the constraint that w1 is binary. We can constrain w2 and w3 similarly. The Geometry Again w1 1 18 19 This is a two dimensional portrayal of the constraints x1/20 ≤ w1 ≤ x1 . 20 x1 Zor’s modified Problem Max 52 x1 + 30 x2 + 20 x3 - 500 w1 – 400 w2 – 300 w3 s.t 2 x1 + 4 x2 + 5 x3 ≤ 100 1 x1 + 1 x2 + 1 x3 ≤ 30 10 x1 + 5 x2 + 2 x3 ≤ 204 x1/20 ≤ w1 ≤ x1 w1 ∈ {0, 1} x2/30 ≤ w2 ≤ x2 w2 ∈ {0, 1} x3/20 ≤ w3 ≤ x3 w3 ∈ {0, 1} x1, x2 , x3 ≥ 0 integer As of this point, we have not modeled Zor’s problem. We have only modeled w1, w2, w3. But the only addition we need is to subtract out the fixed charges for producing gold, silver and bronze. So, the model on this slide is the complete model. General Approach for fixed charges for IPs Suppose that the cost of production for variable j is ⎧0 c( x j ) = ⎨ ⎩f j + c j x j Let ⎧1 wj = ⎨ ⎩0 xj ≥ 1 xj = 0 if x j =0 if x j > 0 Suppose that xj ≤ M for all j. M may be very large. Also assume that xj is integral. minimize f jw j + c j x j subject to xj /M ≤ wj ≤ xj w j ∈ {0,1}. This is a general approach for modeling fixed charges. You will note that we still need an upper bound on xj. Often upper bounds on values are represented by the letter M. It is suggestive that the value is quite large, although it need not be so in any particular model. It turns out that we can omit the constraint wj ≤ xj , and we would still get a valid model. Consider Zor’s problem, and suppose that we dropped the constraint wj ≤ xj. This would be equivalent to permitting Zor to pay for a setup of gold even if he does not produce any. (Zor would not have to pay for the set up. But he would have this option.) Normally, having more options will change an optimization problem. However, in this case, we are granting Zor an option that would never be taken in an optimal solution. So, the option of setting up for gold and not producing it is a worthless option. Put another way, dropping the constraint w1 ≤ x1 would not change Zor’s optimal solution. And we could also drop the constraints w2 ≤ x2 and w3 ≤ x3 . 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? To play Fiver, you can find it in multiple places on the web including http://www.mazeworks.com/fiver/index.htm The game of fiver. Click on (3, 3) Clicking on a circle flips the color of the circle as well as the colors of adjacent circles. The game of fiver. Click on (1, 1) Click on (5, 5) The game of fiver. Next: an optimization problem whose solution solves the problem in the fewest moves. 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. 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. 3 4 5 Ultimately, we want each circle to flip from green to red. Consider for example the circle in location (3, 2). If we click on (3, 1) or (3, 2) or (3, 3) or (2, 2), or (4, 2), it will flip the color of the circle (3, 2). If we click on these five different circles an odd number of times in total, then (3, 2) will end up red. If we click on these circles an even number of times in total, then (3, 2) will end up green. Interestingly, it doesn’t matter when each click occurs. Let’s write the formulation x(i,j) = 1 if I click on the square in row i and column j. x(i,j) = 0 otherwise. We let x(i, j) be the decision variable indicating whether we click on circle (i, j) or not. There is no advantage to clicking on a circle two times since this is equivalent to not clicking on it at all. 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. z This (with a little modification) is an integer program. I want to write that given any square (i, j) that we should click an odd number of times as restricted to 1. (i, j) 2. (i, j-1), the circle to the left 3. (i, j+1), the circle to the right 4. (i-1, j), the circle above it 5. (i+1, j), the circle below it. The notation is not perfect because it is possible that i or j is 1 or 5, in which case (i, j) is not adjacent to four other circles. We bipass this by saying that x(i, j) is 0 whenever i = 0 or 6 or j = 0 or 6. 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. The previous slide is not an integer program. It has a constraint “x(i, j) + x(i, j-1) + x(i, j+1) + x(i-1, j) + x(i+1, j) is odd”. But if a number is odd, it means that we can subtract a non-negative even integer and get 0. We use this fact to create an integer program on this slide. So this model illustrates one more trick in modeling mathematical constraints as integer programming constraints. Should I give away the solution? In slide show mode, you can see the solution. I pretend in class to be clicking as though I am really playing the game of fiver. But this is a PowerPoint slide, and it does not matter where you click. Using Excel Solver to Solve Integer Programs z Add the integrality constraints (or add that a variable is binary) z 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 Some Comments on IP models z There are often multiple ways of modeling the same integer program. z Solvers for integer programs are extremely sensitive to the formulation. (not true for LPs) Summary on Integer Programming z Dramatically improves the modeling capability – Economic indivisibilities – Logical constraints – capital budgeting – games z Not as easy to model z Not as easy to solve. z Next lecture: more IP formulations