Okay, so this is Discrete Optimization and Mixed Integer Program. We'll talk about MIP. So, this is one of these magical tools that we have in optimization, so it's going to be very different from what you have seen so far. And this is a tool, when it works, it's really amazing. And sometimes it works, sometimes it doesn't, but you will see it's really a magical tool. so what I'm going to do in this lecture is give you a basic introduction to Mixed Integer, Mix Integer Program, okay? We call them MIP, okay. I'll talk about MIP all the time today. And then we talk about branch and bound, which is the basic technique to actually solve them, okay. Basic introduction. This is a big field. What I want to give you is the feeling about what this is about okay? So, this is, this is an integer program. So, what you have to think is that it is like linear program. Okay? So, like linear programming. The only difference is that the variable here, have all to be integers. Okay? So, we still have, you know, an objective function that we are minimizing. And we have n variables and m constraints. Okay? So, you see the, you know you see the end variables, you see the end constraint. All these constraints are inequalities okay? So, the variables are constraints to be non negative okay? Again okay? And then we have these additional constraints that they have to be integer values okay? And this difference, this makes a huge difference in practice of course. Okay? So, we'll talk about the mixed integer program when not all the variables have to be integers. Some of them can and some, some are and some aren't, okay? And that's essentially a mixed integer program. So, we have some values that are like in linear programming. They can take you know, rational values, real numbers. Are and then some of them are going to be integers. Okay, so and that's why you call mixed, mixture of two variables. Okay, but once again, a big you know, a big, big thing to mention here is that the constraints are linear, they're qualities and of course we're minimizing. Of course all the techniques that I've shown you for linear programming are still working, right? Maximizing is easy to do. You minimize the negation. Writing equations or you know, inequalities or equations, and, and you know, equations are inequalities. Are going to be done exactly like we did for linear problems. And of course if you want a variable which can take negative value, you can always use a different set we have done before. Okay? So, most of the same technique, but what is key is that the constraints and the objective function are linear. But now, some of the variables can be integers. Okay? So, the difference between having integer variables or not having integer variable is big, right? So, that's the gap between being polynomial and NP complete, okay? So, this is a huge difference, as soon as you introduce this, this, this integer variables okay? So, so the, the, the entire complexity of the problem changes and for most people in industry sometimes, it's a big, it's a big difference right? They say, oh but it should be easier there are fewer integers than there are real numbers but no having integers is what makes this problem really complex. Okay? So, this is an example that we have seen before. Right? The knapsack example. This is, this is a mixed integer program. Okay? So, we have a linear objective function, the variable xi are constrained to be 0 and 1. And they have to be integer value. Want to take the item or not. Okay? You know it's not a fraction value. And of course we had this linear inequality. Okay? So, that's the most simple in a sense. Mixed integer program that we have okay? So, what we're going to do now is look at warehouse location we see this problem before when we do local search. And what we going to do is develop the mid program for it. So, I'm going to go over what the problem is again and then we see how we design. And mid program, actually we'll come back several time to this problem, okay? So, what we had there is that we have various locations where we can open a, a warehouse, okay? So, when we open a, a warehouse in a particular location, we say we open that warehouse. If we don't put it there it's basically, basically say that it's closed. Okay? And then we have a bunch of customers have, you know, around you know, all over the place. Okay? And the goal is actually to choose which warehouses to open so that you can serve all the customers. And every one of the customer. Is,will be allocated to exactly one warehouse okay? Now what you want to minimize is the cost of opening these warehouses and maintaining them, that's the fixed cost for every warehouse, warehouse. And then you have the transportation cost from the customers to the warehouse okay? So, you will want to minimize the sum of these two things okay? So that's the problem okay. So, this one solution where you open one warehouse and you serve all the customers with that warehouse okay? This is another solution where we open two warehouses okay? And the customer are served you know, in the way which is depicted here. But once again you know I want to focus, I, I want to mention the fact that every one customer is assigned to exactly one warehouse. Okay? And this is another solution with two warehouses. It's a different customer allocation. Okay? So, now the question is can we find a MIP model okay? For warehouse location. Okay? And so once again, it's [UNKNOWN] constraint programs. It's going to be easy, right? So, the only three things that we have to do is find what are the decision variables. And then we have to express linear constraints, because we are in a MIP context in terms of this decision variable. And then express the objective function, which is also to be linear. Okay? So, can we find that for warehouse location? Okay, and obviously the answer is yes. Otherwise I wouldn't be talking about this problem, right. So, what are the decision variables? Okay? So, in this particular case we are going to use two types of decision variables. Okay? So, the first type is going to basically be associated with every warehouse. Okay? So right, so this is what we want at the end, we want to know. You know, which warehouse is to be open okay? How many and where, okay? So, we'll have a decision variable xw for every warehouse w. And that variable is going to be one, if that warehouse is open, okay? So, that means that we're building the warehouse at that location, okay? It's zero if we just don't build the warehouse at that location, okay? So, that's the first type of variables that's going to tell us where to build these warehouses. And how many. Okay? Now, we need a second thing, right? So, we need for every customers to know which you know, warehouse it's going to be allocated to. So, we are going to use a second set of variable, which we call the Y variables here. Okay? And Ywc is going to be equal to 1. If customer c is basically served by warehouse w okay? And zero otherwise. Zero would mean, okay custo, warehouse w doesn't serve customer c. Okay? So, once again two types of variables. Whether we open a warehouse or not that's the x variables and the y variables is going to tell me for a pair of customer's warehouse are these two guys connected? You know, is this warehouse serving that customer? Okay?. So, now we the decision variables the only thing that we have to do now is express the constraints okay? So, what are the constraints okay? So think about it. What are the constraints in this particular setting, okay?. Now there is one constraint which is really important that we don't want to miss is that we can serve a customer with a warehouse. Only if that warehouse is open. Right? So, we don't to connect a customer to a warehouse that doesn't exist. Right? So, that's a very simple constraint. Okay? But it's very important. Otherwise you know, we don't, we wouldn't have a solution. And the second one is that we want to make sure that the customer is served by exactly one warehouse. Okay? So, so we have to make sure that the customer is served. But it can only be served by one warehouse. Okay? And so, essentially that's the second constraint, the second type of constraint that we have to express. Okay? Now, we have to express these constraints as linear constraints. Okay? And that's what this slide is showing you. Okay?. So, the first constraint telling you that you know, a warehouse is to be opened to serve a customer, is a simple inequality with two, the two, the two types of variables okay? So, we are basically saying that, why the value c has to be smaller or equal to xw, what does that mean okay? So, if we close the warehouse, so that means that xw, if we close warehouse w so that we don't build a warehouse, that means xw is 0 right? If xw is 0 then it's for, you know y you know, wc is going to be forced to be 0, we can't actually you know, serve that customer with that warehouse. That's part of what we want, right? And if, if xw is 1, that basically means that the warehouse is open, we can use it. But that doesn't mean that we have to allocate customer c to that warehouse, but we can. Okay? So, that value is going to be 1, which basically means that the variable you know, ywc it's free, it can take value 0 it can take value 1. That's the meaning of that constraint. Okay? So, in a sense we are encoding you know, the relationship between these decisions using an inequality in this particular case. And this works well because these two variables take 0, 1 values and we come back to the fact that in a MIP a lot of the decision variables are going to be 0,1. Okay? The second constraint that you see there, is basically telling us that a customer should be served by exactly one warehouse. And what we're going to do is, we're going to look at one customer, we're going to look at all the possible warehouse. And we're going to make sure that the sum of the variables that are basically denoting whether that warehouse is serving that customer, is equal to 1. And that's what you see there, okay? So, you see a sum for all the warehouses. And then you see the variable ywc okay? So, that basically means is y actu, is w actually serving customer c? Okay? So, it's the sum of all these guys and they have to sum to 1. Okay? Once again, these guys are 0, 1 so that basically means that one of these warehouses is going to serve that customer. Okay? So, beautiful we have a model, if we can express the objective function. The objective function now is the sum of the fixed costs and the transportation cost. Okay? It's reasonably easy to state. What you do, this is essentially the fixed part, okay? So, what we are doing is the sum for all the warehouse of the fixed cost of the warehouse, okay, times whether the warehouse is open or not. So, if the warehouse is closed, there is no cost. If the warehouse is open will, you know, incur a cost of cw. Okay? And then the second, the second aspect here is basically the transportation cost. We look at the pair wc, and if, and if, you know, w is serving c, that variable y is going to be 1. So, we want to incur the transportation cost. twc okay? So, that's we have to do, of course with the variable y is 0 then essentially there is no cost incurred. You know, these things are not connected. Okay? So now, so this is the transportation costs okay? So fixed costs, transportation costs. We have the objective function and we have the entire model okay? So, this is the entire MIP model for warehouse location. Okay? Objective function, fixed cost, variable cost. Okay? Then we have the constraints here, that basically state that you know, you can serve a customer with a warehouse. If the warehouse is, if, you can serve a customer with a warehouse if the warehouse is open. Then you have to serve exactly 1 customer uh, [INAUDIBLE] a customer exactly once, so you look at all the warehouse exactly one should serve that customer. And then usually these two types of variables have to be 0 and 1. Okay? We open up a warehouse or we don't, we serve you know, the warehouse w serve customer c or not. Okay? And that's the entire model. Okay? So, so its interesting when you look at these models that the variables here are 0, 1. Okay? And I'm going to come back to that, but we could have another essential model. We could think of you know, instead of having all these 0, 1 variables, ywc for all the warehouses, why don't I have simply a variable yc. Which denotes the, the, the warehouse that is serving customer c, okay? Now this is a question for you, okay? So think, you know, use, you know, try to build a MIP model using a decision variable which is yc, okay? And see what the challenges are. It's a very, it's a very interesting exercise try to see what is going to be tough if you use these decision variables, instead of those 0, 1 variables that I showed you, okay? So, so to think [UNKNOWN] is that in general, MIP models love 0, 1 variables, okay? So, you'll see a huge amount of 0, 1 variables in MIP model. You'll see typically very few integer variables, okay? The integer variables are typically going to be 0 and 1. So, you know, it's like you know, MIP models like to have decision which are actually yes or no, okay? So, very different from constraint programming model in that sense, okay? But the good point is that once you have the 0, 1 variables expressing linear constraints, is typically very simple, okay? So, in a sense you know, you use these very simple 0, 1 variables and then all the constrains. Are you know, simple to state in general. Okay? So, so sometimes they have many indices, but they are easier to state, they are easy to state okay? So, it doesn't mean that you know modeling in MIP is easy. And we'll see some of these issues later on so, there're are still many, many possible models you can design. You know, what are the basic, what are the basic decision variables that you are going to use? What are the constraints? What are the objectives? Everything that we said for constraint programming is still valid. Finding a good model is not necessarily easy, okay? And so, we'll see some of these things in, in a moment, actually, or the next lecture. Okay, so now we have a beautiful MIP model, how do we solve them? Now this has been an active research area for many, many decades, and it's still a very active research area, it's a fascinating area, okay? And so, one of the basic techniques to solve MIP problems okay? Is to use branch and bound. Okay? Remember, branch and bound, we saw that you know, first lecture you have, or second lecture, with bounding, and branching. Okay, bounding is what, is finding an optimistic evaluation of the, of the objective function. Optimistic, optimistic relaxation, we love relaxing, right? And then branching is when, you know, is basically splitting the problem into sub problems, and then apply the same algorithm on the sub products. Okay? So this is the basic two steps. Now what is nice about MIP models is that they have a very, very natural relaxation, okay? Which is linear programming. And that's why we talked about linear programming so much. We have this linear relaxation that we can use as the bonding of as the bonding part of MIP models, of branch and bond for MIP. Okay? So, the key idea is that you going to remove the integrality constraints, and you have a relaxation, okay? So, this is the only thing that you do, right? You look at this big MIP model. If you remove the integrality constraints, what do you have? You have a linear program. You can solve that very fast, and that's what we going to do, okay? So, the bounding path, the optimistic relaxation, is going to be basically relaxing the integer constraints. You wrap your largest set of values that the variable can take, so it's a relaxation. Okay? So, so basically the branch and bound for MIP models is going to be solving the linear relaxation. Okay? At a particular node, you're going to do that, you're going to look at that node. You're going to say, oh, I want to solve the linear relaxation. And if the linear relaxation is worse than the best solutions you have found so far, you can prune that node, that, that node away, okay? It basically means that the associated sub problems to that node is provably sub-optimal. You can get rid of it. Okay? So, if not, okay, so if the, you, you are basically looking at this linear relaxation more closely, and you are looking to see if it has all integer values, which can happen, right? And if that happens, that means that in this large space of solutions, you know, the linear programming relaxation, it throws in an integer value for all of these variables. And that means that you know, obviously it's a solution to the overall MIP problem, well to, for that node, right? And so, essentially you have found a feasible solution and you can obtain the best solution you have found so far, okay? Now if none of these two things apply then you need to branch, okay? And the interesting thing about MIP models, is that they are going to use the linear relaxation to drive or to branch in general. Okay? And so there are many ways to do this, okay so I'm just going to mention one here. But this is also a very active area. How you branch, what do you use, how do you use, do you use the objective function? Do you use the constraints, and so on. But this is the simplest scheme that is using the linear relaxation. So, what you're going to do is you're going to look at this relaxation, and you know that, you know, some of the integer variables have a fractional value, and they should not. Okay? So, what you're going to do is take one of those, okay, which has, let's say, x which has a fractional value f. And what you're going to do is create two set problems. Okay? One of them is going to be saying that x has to be small or equal to the integer which is the smallest, the largest integer which is smaller than f. Okay? So, that's the floor of, of f and okay and that's one of the sub problems, okay? And the other sub problem is going to see that x is greater than the seal of f, that's the smallest integer which is larger than f. Okay? So, these are two sub problems you can add to the, to the set of constraints that you have and then you repeat the branch and bound. Okay? So, the key point here, if you remember constraint programming. Constraint programming was obsessed with constraints, okay? And was basically branching on the, you know, using feasibility information. Here we are obsessed with the objective. We are getting these, good, you know, well, hopefully good. Relaxation of the objective optimistic evaluation of the objective. And then what we use is we use this linear relaxation which is like ooh, you know, this is like a very good solution, okay? But it's not feasible, and trying to use that for branching, okay? So, in a sense we are branching using optimality information, okay? So, summarizing what I just said. Okay, so we are basically focusing on the objective here. Okay, once again I'm exaggerating, of course the MIP system in practice. We'll also focus on some other constraint, but it's good to exaggerate to, you know, drive the point home here. So, we are basically focusing on the objective and the relaxation gives you an optimistic bound all the best value that the MIP can ever get. Okay? The pruning is based obviously on the objective and sub-optimality. Okay? So, when you detect the linear relaxation is not higher than the best solutions you've found, not better than the best solution you've found so far, you just prune it away, okay? And obviously the relaxation has been obtained by relaxing the integer integrality constraints okay? And we have a global view of all the constraints, you know. So, in constraint programming all the constraints were acting, you know independently. Here we relax all the integrality constraints, but when we look at the constraints, we look at them globally. Okay, so we have this linear program, which basically look at the constraints globally, but they just have removed the integrality constraints. Okay? So, in the Knapsack, in a sense, so when you look at the relaxation, what we did, this is basically the MIP model for the knapsack. And the relaxation is only looking at this, you know, 0,1 that you see there, and basically replacing them by the fact that oh, it doesn't have to take the values 0. One, it can take any value between 0 and 1. Okay? That's the linear relaxation and we can do that for any MIP model right? So we just remove these integrality constraints okay? Now, so in the case of the Knapsack, the linear relaxation is the same as the greedy approach that I've shown you right? Order the item by the most value per weight okay, and select them in that order okay? Until you get a fractional value and you take that fractional value. to, to, to get a relaxation. So, that's what the linear programming relaxation is going to do. So, I'm going to talk a lot about this linear programming relaxation the next couple of, of classes. It's a beast and, you know, you see it's, it's, it has very interesting behavior. Okay? Now when we branch, we branch with a fractional value, and essentially in this particular case of the Knapsack, the fractional value is going to be the most. You know the, the item with the, the largest ratio that we can't actually fit in the item. We fit all of the items which are more valuable per weight, right, better ratio. Okay? And then we are basically looking at that last item that we would want to put into the Knapsack, but we could only put in a fraction of it. That's essentially, you know, the, the item we're going to branch on, because this is the only item which will have a fractional value, okay? Now, the question that I have for you, for you to think of at this point, is that ooh, you know, we're going to take two things. These are 0,1 variables, right? So, he's going to be, so that, that the, when we round the fraction downwards or upwards, what you are going to get is essentially 0 on one side and 1 on the other side. So, we are going to not take the item or take the item. So, when we don't take the item, can you think of what the linear relaxation is going to do, okay? So, lot of the games in MIP is going to figure out what these [INAUDIBLE] linear relaxation is going to do. And it's very capricious, you'll see. Okay? So, in a sense here, you know, what I'm asking you, is that if we don't take the item, what's going to happen. Okay, or if we take the item what's going to happen to this linear relaxation, can you figure that out? Okay? So in a sense, the question that I'm asking you is, ooh which value is going to become fractional if you don't take the item? Okay, think about it. I decide not to take the item. All the items that were more valuable, what's going to happen to them? Well, you're going to still take them. And then what you're going to have is a fractional value for one or more, well, yeah, one or more items, later on. Okay? So that's what's going to happen. If you don't take the item. If you take the item, what's happening? Ooh, before you couldn't put this item in the Knapsack. No you decided, I want to take that item. So, that means that some of the items that were before, you won't be able to put inside the Knapsack, okay? And so the, there is going to be a fractional value for an item that was more value that's now going to be, that's now going to be fractional okay? So, this is the kind of reasoning that sometimes you need to think about, you know, what is the linear relaxation doing. Because that will give you insight on how to actually improve your models, okay? So, this is a very simple illustration because this is a really, really simple example but it's going to drive two points home, okay? And, and, you know, you'll see them. So, once again, so we had basically these three, you know, this knapsack with three items, okay? So, the value of the item is Vi, the weight of the item is Wi, your item 1, 2 ,3. Okay? So, most valuable item is item 3. Okay, 35 divided by 3 is pretty good. Okay? Above 10. Okay? So, a 45 divided by 5 is what is 9 and 48 divided by 8 is some, it's around 6 right? And so therefore, you know this is the most valuable item that is the next one and this is the least valuable item from the weights, you know value ratio. Okay? So, at the top of the, at the top of the tree at the root node, what you have is a value of 92 and that value of 92 is basically obtained by selecting item. Well, I think we can let the linear relaxation do this and this is what the linear relaxation does okay? So, the linear relaxation is going to take, you know, value, value one for x1, I'm taking item 1, I'm taking item 3. Okay? So, these are the two, you know, items with the best ratio. And then I take only a fraction on the second item, because I can't put the entire item in okay? And you know once again this is 5 and 3 this is 8 you know I can only take a quarter of that guy. And this is all you get you know, this this value because you, you, you sum 45 and 35 that's 80 and then a quarter of 48 that's 12 that's the value of the linear relaxation. So, this linear relaxing is basically giving you this solution and that particular value. Okay? What are we going to do? Okay? I told you. We look at this thing and we look, ooh, what is the fractional value? And in this particular case, it's item x2 okay? So, we're going to branch on x2, and we're going to create two sub-problems, okay? One where x2 is 0 and one where x2 is 1. Okay? What happens if x2 is 1, is 0, okay? So, that's the node that you see over there. Okay? Now the linear relaxation is 80 okay, you can select only item 1 and 3. Okay? So, we solved the linear relaxation at that node, and what do we obtain? You know, x1 is equal to 1, x2 is equal to 0, x3 is equal to 1. That's the linear relaxation. The linear relaxation here is finding, you know, an integral solution. We know that we don't have to branch anymore. We are fine, okay, this is the best we would be able to do. It's all integral okay, so we don't have to branch anymore. It's done, okay? So, the linear relaxation here is telling you when to stop branching in a sense, okay? So, we have found a solution we evaluated okay? The other thing that we wanted to do, is basically you know, choose x2 is equal to 1, okay? So we basically fix the value of x2 to 1. We solve the linear relaxation again, and the linear relaxation is going to give us a value of 71.33. Okay? You see that now there is this value of this x3 which is fractional, okay, it was actually, it was actually not fractional in the original relaxation, okay? So, we know that this is, we would have to continue branching, but what we have seen here is that the value of the inner relaxation is 71. The best solution that I have [UNKNOWN] so I can actually prune that node away already. So, with one branching essentially I, I solved this problem optimally. Okay? So, this is essentially illustrating the various concept here. At the particular node you solve the linear relaxation. Okay? You look, the value of the linear, the objective function of the linear program is basically giving you an optimistic evaluatoin of what the MIP can do. Okay? At that particular node. Okay? And then you look at the variables over there and you take a fractional variable to actually branch okay? And then you branch left and then you branch right based on that fractional value. Okay? Now, one of the questions that you have to think of is when is branching bound going to be effective? Okay? What is it's going to be really effective is the value of the linear relaxation is tight. It's very, very close if the linear programming relaxation is very close to the optimal value of the MIP. Okay? Is that sufficient? huh? Think about it. So, if I tell you, I guarantee, okay, that this linear relaxation is going to be 0.5%, always of the best value of the MIP. Is that sufficient for the MIP to actually behave nicely all the time? Okay? Question for you. Okay? I wish we had quiz in this class. We don't, but anyway. So think about it. Is it sufficient? Okay? So, what is a good MIP model? A good MIP model is going to be a model which is a good linear relaxation. It's not sufficient necessarily. Okay? I answered that question, right? But this is a necessary condition, you want a model with a very good linear relaxation. Why? Because you're going to prune the search space much better. Okay? Now, which variable should we branch on? So, we have a lot of variables, it seems that we have plenty of variables with fractional values. Which one are we going to branch on? Okay? So, one of the good heuristic is to branch with the most fractional value okay? So why, why would we do that well, you know once again exaggerate. Assume that you variable which is not very fractional okay? So, it's like you know 0.99999999999 okay? And it can take value 0, 1 okay? So, when it is 0.9999999 [UNKNOWN] I hope I you know, use the same number of nines, but that means that it's really close to one, probably branching there doesn't make too much sense. If a variable is 0.5 what does that mean? It means that the linear relaxation is saying, hm, maybe I should take this item hm, maybe I should not take this item hm, I do not really know. Okay? And so therefore these are the type of variables that you need to branch on. Okay? So, this is a basic introduction to MIP. Next time we are going to see really cute things, on how you can actually build MIP model. What does it mean to be a good MIP model? Okay? come back. Thank you.
