Okay, so that's two integer programming formulation. We're going to tell you that with the help of integer variables,or especially binary variables, we may do a lot of things. So again, let's start with our classic knapsack problem. In this particular example that say, let's say we have four items to select from. For each item we have their values, we have their weight, okay? And the knapsack capacity is 10 kilograms. We cannot exceed the knapsack capacity and we want to maximize the total value. So we want to select some out of these four items so that our knapsack is good enough to carry those weights, and we want to maximize the total value. So actually we don't want to really solve this problem because this is just an instance helping us to get into the situation and understand what we want to do. So, if this is our integer program or binary program, pretty much this is an IP, and we understand why it should be an IP, right? Because you cannot carry 70% of item one or 20% of item two. All or nothing. When you have some all or nothing situation, then pretty much you need a binary variable, okay? The thing is that there can be more to be incorporated. So integer programming allows us to implement some selection rules. For example, we may choose at least, or at most some items. Maybe we may say among items 2, 4 band 4, we need to select at least one. If that's the case is very simple. Okay. x2 plus x3 plus x4 must be at least 1. If that's the case then, because each variable is either 0 or 1, this simply says they cannot all be 0. You need to choose at least 1. Similarly, among items, 1, 3 and 4, maybe you may choose at most two. If that's the case, x1 + x3 + x4 is less than or equal to 2. You cannot have all of them to be 1. You may implement the Or condition when you are selecting variables. What's that? For example, maybe I may say, okay, I need to choose either item 2 or item 3. Well, this simply means at least one out of these two items. So it's nothing but x2 + x3 must be at least 1. Or interestingly, you need to select item 2. Or if you don't do that, you need to select item 3 and 4 together. So this is a little bit more complicated but nothing too complicated. You may write it in this way, 2x1 plus x3 plus x4 is greater than or equal to 2. If your x2 is 1, then you are done. There's no requirement for you in x3 and x4. But if your x2 is 0, this tells you that both x3 and x4 must be exactly 1, okay? So this allows you to do a selection criteria like this. Or we may implement If else. If else means if you select item 2, you need to select also item 3, something like that. Then we may implement it in this way. So if x2 is 0, you have no requirement on x3. It's up to you whether to take item 3. But if you want to take item 2 and item 2 is set to 1, then your x3 must be at least 1. So similarly we may say if item 1 is selected, you cannot select items 3 and 4. How to do that? In this way. So if your x1 is 0, then you are having to greater than or equal to x3 + x4. This simply means there's no requirement on x3 and x4. Is up to you to bring them or not. But if your x1 is 1, then the left-hand side would become 0, this means you cannot take x3 and x4. So many kinds of variable selection or item selection criteria may be implemented, if you have some careful arrangement about these binary variables. So similarly, while we can choose variables, we may also choose constraints, or we may choose constraints in some flexible way. So let's say, I want to satisfy one of the two constraints, this one and that one. I need to choose one of them to be satisfied. I don't need to satisfy both but I need to satisfy one of them, okay? So this looks like a union, or compare it to in the past that we doing intersection, okay? When we are doing intersection, if we say we need to satisfy both constraints, we are talking about the intersections. But when we are having this particular case we are talking about union, okay? So either you satisfy this constraint, or you satisfy that constraint, both are fine. Obviously, this is not something a linear program can do. So that's why we need to deal with binary variables. Okay, so let's see how to do this. So first, I'm going to define a binary variable z, which is representing whether I satisfy constraint 1 or whether I satisfy constraint 2. If I satisfy constraint 1, I say z is 0. Or if I satisfy constraint 2, I say z is 1. One thing is important is that please take a look at the way this is defined. If g1(x) is less than or equal to b1, you say z must be 0. That does not mean you cannot have the other constraint satisfied, okay? So, this definition allows you to satisfy both constraint actually. Okay, so this is a definition, let's see how to make it work. So let's first assume we have a very big number, Mi. And if that's the case, then the following two constraints would implement the thing we want here. So what's this? Suppose z is 0. In that case, this guy becomes 0, this guy becomes m2, right? When the first constraint becomes 0, that simply means you are g1(x) must be less than or equal to b1. So your constraint 1 must be satisfied. And then because M2 is a very large number, which is an upper bound of the left-hand side. So that means you may do whatever you like on X. There's no way for this thing to be greater than M2. Okay, so when you make the first right-hand side 0, you say that constraint 1 must be satisfied. When you make the right-hand side for the second constraint to be M2, you are saying that you don't care about constraint 2. It may or may not be satisfied due to of x may be greater than b2 or less than b2. But pretty much with this M2 there, you don't care. So similarly if your z is 1, then the thing simply changes for constraint 1, this left-hand side is only required to be less than or equal to a very large number, so it always will be satisfied. It doesn't really matter whether g1 is greater than b one or less than b1. And then your right-hand side for constraint 2 would become 0. This requires you to really make g2 of x less than or equal to b2, okay? Then because your z must be either 0 or 1, when your z is 0, you must satisfy constraint 1. When your z is 1, you must satisfy constraint 2. This requires you to satisfy at least one of the two constraints, okay? Then you satisfy one of them. So similarly, suppose you have three constraints, you need to satisfy at least two, then what should we do? Okay, let's play the same trick. I'm going to define zi as 0 and 1, but now instead of having one variable facing two constraints, I'm going to have one variable facing one constraint. So, I'm going to have z1, z2 and z3, okay? So for z1, z1 is 1 if I want to satisfy constraint one. So again, let's say M is very large numbers, then in that case, if z1 is 1, I'm going to make this part 0, okay? And then this is required to be satisfied. g1 would be required to be less than or equal to b1 for the other. Two constraints is the same thing, and I impose the constraint here, saying that among z1, z2, and z3 at least two of them must be 1. So that means at least two of these constraints must be satisfied, okay? So there's one thing to remind you is that you need to have an Mi, which is a very large number. Very large here means you need to make sure that is if your zi is 0, so that you are having this constraint. You need to make sure that there is no way for your left-hand side, for your left-hand side to be greater than your Mi, okay? That's something required for you to choose Mi. Mi is a parameter. You need to set up the value for Mi by first doing some analysis on the performance, on the behavior of g. So later we will have some other examples here, just assume that you know there is a big enough Mi, so that you may make these kind of constraints selection be realized or be possible.
