Okay guys. Discrete Optimization Part VI, okay? So, once again what we're going to do is using the tools that we have built so far and trying to build better models, okay? So, we know some of the techniques that we have, and what I want to show you today is how to use redundant constraints to speed up models tremendously, okay? Now what is a redundant constraints? Okay, so essential these are constraints that don't add anything to your model from a semantics stand point. The model will have the same exact number of solutions, okay? But they are computationally significant because they will prove the search spacement role. So in a sense, so you put them in the model. They don't remove solution, but they decrease the search space. And so once you find these constraints, they are very, very useful from a computational standpoint. Of course, the question is how do I find that? And in general, they capture really interesting properties of the solution. You look at your problem and you say, oh, but four, you know something to be a feasible solution it has to satisfy this. And typically that's a constraint, you take that constraints. You've put it in the model and in Constraint Programming the more you put inside the model the faster your compilation is going to be. So it's a pretty good aspect of Constraint Programming. Most of the time you try to capture as tightly as possible this set of solutions by expressing the constraints as best as you can, okay? So I'm going to use a couple of simple examples, you know to illustrate this. You know, remember the magic series, okay? So we want you to find numbers from S0 to Sn such that Si represent the number of occurrences of i inside the series, okay? So I asked you last time you, we could actually find this series, this is a beautiful one, okay? So we see you know, there are two instances of 0, took, took, there is one instance of one itself, there is two instances of two you know, itself. And the first one, okay? And there are reviews 0 instan, 0 occurrences of 3, 0 occurrences of 4, okay? Now, so this is the model that we saw last time. And what I was you know? One of the things that I'm asking you, is, can you find the properties that the solutions have to satisfy. Now when you look at the, you know, the array of decision variables series. Can you find a constraints that is actually helping, you know, will help, you know, in addition to these constraints that we have, that we have stated. So we have these constraints which are stated, it actually capture exactly what are the solution. But can I, can I find another constraint which is always true for every solution, but which will give the solver much more information? And that basically means the solver will be ab, able to explore it to remove values from the domain of the variables. Because that's the end of you know, that's the rule of the game essentially, okay? So, typically you know, the way you do this is that you exaggerate, right? So look at this thing, okay? So this is my magic series and I'm asking you, can I put 17 there, right? I'm exaggerating right, so nobody would do that, okay? I put 2000 there, you know, it makes no sense. Why? Because what is 17 denoting there? 17 would denote the number of occurrences of 4 in the series, no that series is you know 5, of length 5. If I put 17 of [UNKNOWN] on one variable to put 17 occurrences of 4, okay? So, in a sense, what do I know? Can I get you something which is interesting on the sum of the numbers on this series? Yes, they are all occurrences. How many occurrence can I have? Well the length of the series, okay? So I can have this beautiful essentially constraint which says that the sum of all the elements in the series have to be equal to the length of the series which is n, okay? So these constraints has to be true, it must be true, there is no other way. Okay, so the number of occurrences n, okay? And since these guys, these decision variables, are denoting the number of occurrences okay, the sum of them can not be more than n. So this is a constraint which is redundant from a semantic standpoint. It will never, never remove any solutions. Every solution will satisfy those constraints. But it will be able to prune the search base better, okay? So, can I do better than this, okay? Can I find actually something which is stronger than that? Look at this thing, okay? So what am I writing? Assume that series 2 is equal to 3. What does that really mean? That basically means that the value here, okay. I'm going to put the 3 over there, okay? What does it mean? It means, essentially, that there are 3, 2 in this array, okay? So far so good, that's what we know. But saying that there are three, two's in this array means what? How many occurrences that, that call for. Well essentially, you know, these guys, you know, there are three two's, okay? Two occurrences, and there are that three times, so that means there are six occurrences, okay? So essentially what we know is that there is another way for actually counting the number of occurrences. Instead of summing every element in the series, what you could do is look at the re-element in the series, okay? And then multiply by i. So you look at every element of the series, let's say element i, and you multiply it by i, because what you, what I had before was what, series two was three. So, I multiplied by two, so that makes six occurrences, okay? So it's another way of computing the same information, okay? So I have another redundant constraint, which is basically the summation of i, you know, times series i, has to be equal to the number of occurrences, which is n, okay? So that's another concern, which one of the two that I've shown you before is stronger, okay? I will tell you a little bit which one is stronger, okay? But it doesn't matter, right? We could put the first one, we could put the second one inside the server and let the server propagate these two, two constraints at the same time. Okay, so let me show you the kind of deduction that we can do. Okay, so this is essentially only taking the second one here, okay? Which is stronger in almost all the cases, there's one case where it is not, but almost all the cases it is stronger. So you see essentially the constraint reduction before, but you see this redundant constraint which is over there. Okay, what is interesting is what? You see a five there and you see that this guy is multiplied by four, right? What does that mean? Okay, that means that the maximum value that series 4 can take is what? Well, it's one, right? And the same thing for series 3, and for series 2 the maximum value is going to be two, okay? Otherwise I will exceed these five, okay? And for one it's going to be, you know, five, okay? So immediately, I can deduce very strong information here, on the value of these variables, okay? And I can use that for pruning the search page [SOUND]. Very quickly, many of these ray file constraints can disappear, okay? Because I know that they can't be true, okay? So essentially, here, you know, I have removed about a third of these constraints, okay? Then, assume that I make a very simple choice. I say that series 0 is equal to 2, okay? So that basically means that I put a 2 over there, right? So, you see the 2 over there, okay? It also means that I have a 2, right? And therefore, the value that we see here for series 2 here I have already one over there, okay? And then, you look at the constraints, you know, the redundant constraints that I have added, okay? So, what do you see there? I know that series 2 is greater than 0 now, okay? So, and therefore, when you look at these constraints, essentially the 5 has become a 3, okay? And therefore, I can immediately deduce, okay, that series 4 here has to be equal to 0. Because it multiplied by a coefficient 4, and it can be at most 3, and that the other one, the 3 times series, 3 can be at most, you know, 1, okay? So once again, I can use that information and I can start propagating that information, and my search base becomes much smaller, okay? So, if you use the simple model that I've just shown you, you can solve magic series up to really, really large numbers. And if you do that, if you actually implement this beautiful model, you will see a very nice pattern in the way these solutions are actually being so, so, so basically constructed. And the similarities that they have with each other. Okay, so the first role of Redundant Constraints is to express properties of the solution. And because it, it looks at the problem, the redundant constraint is looking at the problem from a different angle, it's going to boost the propagation. Okay, so in a sense what you are, you know, what you are adding is this new constraint inside the overall model. You had all these constraints which were already there. They were proving the search case independently. You add the new one and that one will also reduce these domains and therefore will have an impact on the other one. That's the first rule of redundant constraint, okay? So, I'm going to show you another role, this is the second role, which is to provide a global view, a more global view okay? So, and what I'm going to show you is that you can actually combine existing constraints. And that combination will improve your communication between the various variables okay? So, this is, I'm going to illustrate with a market split problem, okay? and essentially once again, so you can think of it as a multi knapsack except that the constraints, instead of being small or equal are going to be equal, okay? So what you have is a set of constraints, a set of you know, you will have a set of constraints, you know, indexed by C, a set of variables indexed by V, okay? For every value in C and V, you will have have essentially a weight, okay? You can think of an abstract in the multiple dimensions, dimensions, that's a WCV, okay? And then you have a right in sight, you can think of it as a capacity, okay? And then the decision variables are going to be this value X. There is one variable for every element of V, okay? And then the constraints are essentially kind of knapsack constraints except that it's an equality and not a second equal. But what you do is you basically multiply the weight and the variable, okay, for everyone of these concerns. And you want that to be equal to the right hand side, okay? Now these constraints are actually pretty, pretty weak from a, from a propagation standpoint. They don't communicate each, to each other, only through the domain. And in this particular case, you have this linear concern that I'm basically doing their work independently. And they communicate very later, okay? So one of the thing you can do, okay, is use the concept of surrogate constraints. So you take all these constraints and you add them, everyone with a different coefficient, okay? So I'm basically using here, you know, alpha to the power of C, okay? And by essentially multiplying the first constraint by alpha, the second constraint by alpha squared, the total constraint by alpha cubed, and so on, okay? I can combine all these constraints. I also multiply the right, the right sorry, the right insight here. And therefore, this is essentially a combination of all the, a linear combination of all the existing constraints, and it's valid, obviously. It's not going to remove any solution, and I can add it to the solver. So what I did was essentially take in constraints that are completely independent, merging them together. And now they are working on the same set of variables and they are going to prove the search base more, okay? So, Surrogate constraints, using Constraint Programming they are using Mathematically Programming as well we might talk about that later on, okay. But essentially what I'm doing is simple combination you know in this particular case, linear combination of existing constraints, okay? So in a sense, a Surrogate constraints is just a new constraint that I add, like the properties of the solution that I shown you before. Except that this time I'm not expressing a properties of the solution per say as something that I discover. I simply taking existing constraints and combining them and getting this new constraints that I am putting inside a constraint ,solver. Once again by definition, if I add new constraints the only thing that can happen is that I prove more in the worst case I prove the same, okay? And so in some application, it can make a big difference. Thank you.