Okay, this is discrete optimization constraint programming part two. Okay, so this is the goal of the lectures, of the lecture. Okay, so we're going to illustrate more complex constraint propagation. And the underlying topic is the fact that every one of the constraints in a constraint programming system has a dedicated algorithm, okay? So that's, so basically, that's the technical part, okay? So what are we going to do from a non technical standpoint, is that, for the first time, you're going to see a complex propagation algorithm if you have never seen any. And it's kind of amazing how, how these things are working. The kind of information that you are deducing. It's, like, you know, the first time you see this, it's like, wow, this program is actually pretty bright, okay? Of course, it's not, but, anyway, so it's going to give you a sense of what a constraint propagation algorithm is doing. It's kind of interesting. Okay, so remember, in constraint programming is this combination of branch and prune. Pruning is removing value from the domain of the variables in a first approximation. Branching is, oh, you're stuck. There is no propagation. You decide whether, you know, you assign a value. You decide to split the problems into sub-problems. Typically, you take a values and you start giving all kinds of values for it. You know, in turn. Okay? and then obviously, you know, once you branch you apply the constraint propagation algorithm to prune the search space again. Now, pruning is basically, as I told you, you are using the constraints while, you know, removing as many values from the domain of as many variables as possible. Okay? Branching is, you know, in, in our first approximation we'll see most sophisticated branches came later on, later on, but essentially trying possible, you know, trying possible values for the variables. Okay? Remember with this beautiful separation between the search engine and the, the constraint, the constraint store. Okay? And so what is happening is this guy is basically trying to see if the constraint is satisfiable. And when it, when it tries to derive as much information as it can. The search will make a choice and send a new constraint. And the constraint store is to be able to say yes or no. Okay? Am I still feasible, okay, or not? Am I infeasible, or am I infeasible, okay? And if it's feasible, if you believe it's feasible, you're going to say yeah, it's fine, you know, as far as I can tell I'm feasible. And sometimes, you know, you add a new constraint and then the system will say oh, no, no, I'm infeasble. You know, remove that choice, give me another choice. Okay. So that's basically the essence of, of constraint programming. The inside of this constraint store is very interesting. All right. So you have the domain store here, which is basically capturing the search space, typically associated domains to every one of the variables. And then gravitating around it are the, all these constraints. Okay? And they don't know about each other, and that's the key point. Okay? And these constraints have two goals in life. I told you they basically are asking themselves, oh, am I feasible with respect to this field of, of domains? So can I find an assignment for the variables using these domains such that, you know, I'm, you know, this constraint is satisfied? And then they will say, oh, but can I actually knock down some values in these domains, such that I reduce the search space, okay. And of course, as soon as you do that, some of the constraints may become infeasible, or some of the constraints may be able to knock down more values from these domains. And that's the constraint propagation algorithm, okay. Right, the constraint does two things. Feasibility checking, you know, is it still feasible in the set, we're given the set of domains. And then pruning, given a set of domains, can I knock down some value for the domains of the other variables. Okay, now the key point, and this is one of the topic, one of the topics covered today, is that every one of the constraints in a constraint programming system, has a dedicated algorithm to do, these two tasks. Okay? It's going to test feasibility, using the semantics, the structural the constraints, and it's going to do pruning using the same information. Okay. So we, so this is the strength of constraint programming. You can, can explore the structure of these constraints to prune the search base as best as it can. So I'm going to use a very simple example, send more money. The story here is that, you know, this is a graduate student going to going to school. You know, he needs more money, so his father is very, and his mother is very reluctant to actually give him money. And so every time he asks for money he has to find a clever way of asking. And so here he's sent, you know, his parents a puzzle and that puzzle is, you know, if the parents solve the puzzle, they will know how much money the graduate student wants, okay? So that's the story. So, essentially the person has, you know, three words, send more money, okay, all right? And the amount of money has to be essentially the value of these letters over there. And you have to make sure, of course, that the addition here is valid, okay? So in a sense you have to assign different digits to all these letters, such that addition is valid. And then you will have, you know, essentially the amount that needs to be sent. Okay? So, now I'm going to show one model, okay, for solving this puzzle using constraint programming. It's not a good model, okay, but it's, it's just, you know, a model for illustrating constraint propagation. So, big disclaimer in many of the, many of the examples that I'm going to use, the entire, you know, class, is that there are many, many models that should be better than the ones that I'm proposing. They are typically chosen to illustrate different principles. Okay, so this a model like we would do in kindergarten, in the sense that I'm going to do, you know, column-wise, you know, digit-wise addition and use carries. Okay. So when you look at this thing here, okay, so you can see that you know, I'm going to start with the value d and e and summing to y. Okay? I'm going to get a carry c 1. Okay? And that carry is basically going to, you know, be used for the second, for the second column. And then, I'm going to generate another carry for the subsequent one and so on. Okay? So, in a sense, the decision variables here are going to be of two types. They are going to be the letters, okay the initial letters of the puzzle, and then they're going to be the carries, okay? And the letters can take the value between 0 and 9, they are digits, okay? And the carries of course will take the value 0 and 1, okay? So, that's the basic principle here. Okay? And so this is one of the models, okay, that, that, that you could write. I told you this is not the best model that you could write, but this is the model that will illustrate constraint propagation nicely. Okay, so what you see at the top over there, okay, so these are basically all the letters that you have, okay. So so, so in this particular case you have you know, the letter s, the letter e, the letter, you know, n, and so on and so forth. You have them arranged for the digit between 0 and 9. And then you have the two sets of these different variables. Okay, so you see that this is a variable value for every one of these letters, okay, which have to be digits, okay, between 0 and 9. Okay, so for every one of these letters that you see at the top, you will assign a particular digit. Okay? And then you have the carries. There are four of them. And the value of them, for the carries is 0 or 1. And then what you see here are the constraints for the problems, okay? So the first ones are basically telling you that all the letters have to be given a different digit, okay? So this is like you know in the map coloring or in the, in the Queens problem, okay? Basically not equal constraint between all the variables. Then you see that the value for s and for n have to be different from 0. These are the most significant digits of these two numbers. You want them to be different from 0. Then you have the value that the carry for the last carry has to be equal to m. When you actually look at this particular equation. Okay, so this is the last column. And then, and then, essentially you have all the other constraints that are looking at every one of the column and putting and, and expressing the addition. And it's always, in general, it's always one carry plus, you know, a couple of a couple of digits, okay, for, for the letters. And then on the other side you will have one other digit. And you will have essentially 10 times the carry. And that's what you see for every one of these constraints. So you always see the ten times the carry at the end of the equation. Okay? So that's essentially the model here. Okay? So it's a set of not equal constraints, an equation, and then a set of other equations carrying you know the, basically, every one of the addition for every one of these columns. Okay? So this is the search space. Okay? So the search space, initially, what you see there are all the digit values, okay, and you see all the letters over here. You see also the carries there, and these carries can take only the values 0 and 1. Okay, and once again, you know the key point here is that we are going to knock down many, many, many values from this search page, and that's the goal. And in this particular case, there are two things that are going to be interesting. It's how much we prune, okay, using these, these constraints. And it's also the constraint propagation itself. We're going to do something with one constraint that are going to wake up another one which is going to propagate again and so on and so forth. And that's this kind of propagation which is interesting. And this is what we are trying to illustrate today. Okay. So, this is essentially the beginning of the, of the propagation. Okay. So you have the not equal constraints. These not equal constraints are not doing anything initially, because the variables have all the possible values. And then you have this interesting thing here that you know, basically s and m cannot be 0. Okay? And then that m has to be equal to a carry. Okay? So, there are a couple of interesting things are going to happen there. Okay? So, when you see, you know, that m that s cannot be 0, you're going to knock down the value 0 from s. When it, you know, m is not equal to 0, you just knock down the value 0 from m. And then you have this interesting constraint, which is basically saying that the carry four is equal to the digit assigned to m, okay. Now, the carry is 0 and 1, okay. At this point, essentially m is 1 to 9, so there is only one value which is common to these things, and that's and that's the value, and that's the value 1. So these two guys are going to be assigned to 1, okay? And that's what you see here. Immediately, the system is deducing that. Okay? And usually once you do that, you know m, you know every, every digit, every letter, of course has only one value, all the other values are ruled out. We also know that all the digits have to be different, okay? So basically these non equal constraints are going to propagate and remove the value one for all the other, all the other letters. Okay? And that's essentially the state of the search space after this you know, a couple, you know, this not equal and this equality constraint. The last equality constraint that you saw there, okay? So not very interesting you know, right now. This is mostly what we have seen before. So things are going to get more interesting when you see this actual equation over there, right? And so now, we have to find a way to actually process that equation, okay? So I'm here right. And this is the equation on top of me, okay? So one of the things that we're first going to do is to take this equation and simplify it given the current state of the search space. Right? So we know that m is the value 1, so when we see, you know, the value of m we can replace that by the value of 1. So the equation becomes a little bit simpler, okay? And now what we're going to compute is, we're going to, to make sure that this constraint can be satisfied, we're going to compute the value, the, the, the set of values at the left of the equations and the set of values at the right of the equation. Okay? And obviously, these, you know there has to be a non-empty intersection between these two things. Okay? So, we're going to compute the range of, of the left, and the range of the right of the equation, okay. So the range of the left is 3, 11, okay. And I want to go slowly and tell you how we get that, because this is kind of interesting, okay. So, we have to, so this is essentially how you compute it, okay. And every one of these values that you see there is computed in a very systematic fashion, okay. So, look, the 0, which comes here, okay, the 0 is from there, comes from the value of the carry, of carry of the carry 3. So we have two possible values for carry 3, 0, and 1, okay? Now if we try to bounce, you know, to have the smallest possible value for this left turn, we take the smallest value for carry 3 and that's 0. And that is the 0 that you see there. Okay? So the value 2 there is the same thing for s. Okay? So we look at, what is the smallest value that s can take and that is what you see over there. And then usually we get the 1 that is the value of m that, you know, that is already fixed. Okay? And so this is the lower bound on the value of this expression in the current search space. Now, we do the same thing for the upper bounds. And in the upper bound, what you are trying to do is to find a maximum value for that term. Okay? So when we see a variable like this carry three, we take the largest value, and this particle case, it's 1. Okay? then we do the same thing for, the value of s. which is, which is nine. Okay? And that is the value that you see there. the value that you see there. Okay. So that's a value of 9. And then we also have the 1 which comes from the value of m. Okay, and that's how you get 3 to 11, okay. And we can do that, and we can do that for the others, right, which is basically giving us 10 to 19. I won't go into details, I won't bore you into the details, but at this point, essentially, I know what is the range of the left side. I know what is the range the right side. Now, to have a solution to these constraints, the intersections between these left and the range of the left and the range of the right side have to be non empty. And so this is what I'm computing here. I'm basically looking at these two ranges, and taking the intersection. And the intersection has to be, you know, 10, 10, 10 and 10 to 11, okay? So now, I know that this intersection is not empty, so at this point, you know, I believe that there is a solution, okay. So I also know more information. I know that this term here has to range between 10 and 11. If I have a solution. And same thing of course, for the other term. So I'm going to use that information to start pruning the search space. Okay? So what I know is that, if I take the left term, okay? I know that it has to range between 10 and 11, okay? And now, I'm trying to say, oh, but how can I prune the search base using that, okay? So let's, you know, remove all the mass. And now I have just this equation there, okay? And I see that, you know, 10 has to be smaller or equal to the carry 3 plus the value of s plus 1. And that is to be smaller or equal to 11, okay? Now, let's assume that I'm trying to prune, you know, to prune the value of s. What can I do? Well I can first you know, take the 1 which is in the equation and move it on the right and the left-hand side. And then I have to say, oh, I have to remove this carry 3, right? So I'm going to push carry 3 on the left and a carry 3 on the right as well. And so now, the value of s can be bounded by these two expressions that you see there, right? And so what I have to do now, is once again, you know, I want to be very conservative here, right? So I want to see what is the smallest value that s can take, okay? And I also want to see, but what is the largest value that s can take? So when I evaluate this expression, I have to find a way to find the smallest possible value, because if I'm not conservative, I can prune solutions that, I can prune solutions. And the only thing that I want to do is prune values which appear in no solutions. Okay? So what I'm going to do here is to look and say, okay, the left-hand side, okay, has to be made as small as possible. How do I do that? Well I have a minus you know, carry 3. So I have to make this, this carry 3 as large as possible, because if it's large then I subtract a lot of values, and that value becomes very small. Okay? So how do I make carry 3 as large as possible? I take the value 1 for that, okay. And I take the value 0 to make it as small as possible, such that I have the largest term on, on, on the right of the equations. So essentially what I get there is that the value of s has to be essentially a greater or equal to 8, and smaller or equal to 10. So this interesting, right? So because at this point I can prune the search base dramatically for s, right? So I remove all these values up to 8 and 9, okay? And this is what this equation has told you, and I have only looked at one side of this equation, essentially, right? So if I look at the other side, okay? I know, you know, I have to make sure that this side, now, also range between 10 and 11, okay? And so, so I can do exactly the same reasoning, okay? So I take these two things, I put them there. And assume that I'm interested here in looking I know already that the carry 4 is equal to 1. So I get this expression here. Okay? And then I can prove the value of, of o at this point, okay? And basically, it becomes the, you know o is to be basically, between 0 and 1. And I can, in one step, prune a lot of value for o as well. Okay? So all these values here you know, for letter o have been removed. At that point, there is only one left, which is 0, so I'm going to assign it. As soon as I assign it, all the not equal constraints, you know linked to that variable are going to stop because now that variable is only one value. That's when this pr, you know, this, this, these contraints are propagating. Remember last lecture, okay. And so, in a sense, all the other values, all the other variables there are going to propagate there, using these not equal constraints, okay. So, that's what you see there. Okay, so we go back to these constraints there, propagate them, and now the search space has been reduced. And the only variable, the only digit, the only letters that can take the value 0 is o, okay. So that's, so what we have done so far is propagating all the constraints up to the one which is highlighted there. Okay, so we propagated the non-equality, the very simple equality, the first equation, and we are looking at the second one now, okay. Second one is exactly the same reasoning. As I have shown you. We are looking at these equations like that, and we are going to do the bound reasoning that I've shown you. Right? We simplify it a little bit using the value of the variable. We know that this guy is between 2 and 10. Okay? If this guy is between 2 and 10, we know that this guy, to satisfy the constraints, has to be between 2 and 10. And that's what we are looking at. Okay? So now we know the value of n. Okay, plus 10 times the carry 3 has to be between 2 and 10. Okay? So let's assume that we are interested in carry 3. If we are interested in carry 3, we have to take this value of n and move it on the left and the right, okay. So that's what we do, okay? And this is what we get. We get 10 time carry 3 there, okay? And then you have the value On the left and the value on the right for the lower and upper bound, okay? Now you look at this 10 times carry 3, so once again we have to make this guy as small as possible and this guy as large as possible to be conservative right? Okay, so to make this guy as small as possible, what do we do? We take the largest value for n, what is the largest value for n? It's 9, okay? So and, the other side, the upper bound, we have to make it as large as possible. And so, since this value's negated, we have to make it as small as possible so we will take the value 2. Okay? So at this point, we simplified the equation, okay, which becomes, you know, -7 is smaller equal to 10 times carry 3, smaller or equal to 8. The left side is boring, okay, so the right side is more interesting, because its fourth is carry 3 to be equal to what? To be equal to 0. Okay? So, this guy is not going to be 1, it's going to be 0. And now, something really interesting happens. Right? So, what we did, what we just did now, is looking at this second ineq, the second equations, and we found a new value here for carry 3. Now, the interesting point here is that carry 3 is also happening in the first equation. So, now, we are basically saying oh, but that equation has some more information. So I will go back and propagate that information. Okay. So remember the fixed point algorithm is always looking at this loop, and always taking, you know, looking at the constraints and until you cannot propagate at anything, it's going to look at constraints and trying to actually propagate them again. Now when a value of variable like, oof, I show you here, okay, has changed, it's a good indication that you should actually reconsider that constraint. So the constrain propagation algorithm is going to take that constraint and try to propagate it again and try to obviously to find if its still feasible and so on. Okay? So we're going to go back to that constraint. So this is the constraint that you see there. [NOISE] Okay? And we're going to simplify it, because we have a lot more information at this point, right? So you see the, the value of carry 4, we know, we know the value of o, we know the value of n. And so, this constraint becomes really simple at this point. It becomes essentially the value of s is equal to 9, okay? So once again, what we can do is prune the search page, okay? And the remove the value 8 from the value of s, assign the value 9. Of course you are going to propagate all the non-equal constraints and remove all these values. And this is all the search space has removed, okay, has been pruned at this point, okay. So essentially what I have shown you here is all these constraints are basically you know, influencing every other ones. Okay? So, constraints are going to propagate. Okay? Use it's dedicated algorithm to remove value from the variables. Now, some of these variables appear in other constraints. These other constraints are going to be propagated again. Remove more values, which are going to propagate other constraints, and so on. And this fixed point algorithm is really what is the core of constraint programming. So you basically propagate all these constraints until you cannot deduce anything. And also, you have a dedicated algorithm for every one of these constraints. Okay? So, let me go into the, the, the, the, a little bit of the mathematical details to actually implement this. Which are reasonably simple here. Okay? So, this is essentially a cons, this is a linear inequality that I'm going to show you how to propagate optimally. Okay? So, you see that the left-hand, the left-hand side here is basically a sum of product. Okay? A, i, you know, x i. X i, a decision variable, a i is basically constant. So that's the left-hand side, the right-hand side is similar. The y's are basically decision variables, the b's are constant, okay? So what I'm interested in, what I'm interested in here is essentially propagating that constraint optimally. Removing as many values as I can, from the domain of the variables. So I'm going to assume that the domain of x i and, and y i are denoted with the convention that I used last time. So d x i is the domain of x i. And d y i, y j is the domain of y j. And now what I have to do is propagate using that information these constraints, okay? So the first thing that I have to do is to test if it's feasible, okay? And the feasibility test here is going to be very, very simple, right? So how do I make sure that I can, how do I test, you know, if this constraint is feasible given these domains for these variables. Well, what I want to do is essentially take the left-hand side and make it as large, as large as possible, right? And take the right-hand side, and making it small, as small as possible. And if, if by, if the smallest values and the largest values don't satisfy the constraints, I know that nothing will satisfy the constraints, okay? So, the feasibility test. Look at the left-hand side and replace every decision variable by the maximum value I can take. If look at the right-hand side and look at every decision variables, and take the smallest value that it can take. So that's the min in this domain and then I test. Now I have no decision variable left, only constant. And I'm basically test if this is, this, this inequality is satisfied or not. Okay? If it's satisfied, feasible, if it's not, it's infeasible. Right? So, now essentially, I, let's assume that it satisfies all. Okay? Otherwise, I can't prune. Right? I already pruned the note in a sense. And so what I'm going to assume here for pruning, is that I have two values left, l and r, for left and right. Okay? Which are basically, the l is basically denoting the largest value that the left-hand side can take. And r is denoting the smallest value that r can take. Okay? So I'm going to use that for the pruning algorithm. You remember, l is the largest value for the, for the left-hand side. r is the smallest value for the right-hand side. Okay? So then this is how I prune the search space. Okay? So I want to look at x i. Okay? So let's, let's look at x x i. Okay? So what I know is that a i x i has to be greater than what? So, look at this, look at the, the, the initial constraints over there. I'm going to look at the right, I'm going to look at the right-hand side. So the right-hand side is r, okay, so that's going to always be there. And then, what I have to do is take all the other variables here, okay, and move it on the other side, so this, they have the largest value there. And those values are essentially l, except that, I don't want to double count x i, right? So I have to, I have already counted inside, I have already counted inside l, so I have to remove it. I have to remove a i times the domain of times the largest value in the domain of x of, of the, of x i. And that's what I'm doing in this expression here, right? And so now, I know that, I know that this is valid. Okay? So, I know that a i xi has to be greater than that for the constraint to be satisfied. And that leaves me this pruning rule that you have here. Okay? So, I basically take this expression divided by by a i. And since I want to be conservative, I have to run, well, well, that, that, that's fine. So, since I'm working with integers I have to run up of course, if it's a fractional values. Okay? And this is what you see here. Okay? So, this is what you see here, sorry. so what you see there, is that I'm basically taking the seal of that expression over here. Okay? And this is how I prune. And of course, y, for y I"m going to do exactly the same thing, except that I"m going to do, I'm, I'm going to, I'm going to subtract the value of y j. And then I'm going to divide by, you know, b j. And then I'll, instead of taking the the, the ceil, I'm going to take the floor. And I'm going to basically update the upper bound of y j. So in a sense, so what I do is that I update, the lower bound of the axis, I update the higher bound, the upper bound of the y's, using these two very simple rules that can be computed efficiently, which essentially, you know, as I told you, use the largest value for the x i, in the domain of the x i, and the smallest value in the domain of the y i. Okay? So lessons from this lecture. First that, you know, you have a dedicated algorithm for every one of the constraints. The constraint propagation algorithm is really rich, it's going to propagate these constraints until you cannot get information. And so as soon as you accumulate raw information in one variable, it's going to propagate to another one, it can come back and propagate all these contracts, okay. And this, and in this particular case, the bound propagation algorithm is very easy to compute. It's basically reason about, you know, the, the, the upper bounds and the lower bounds on every one of the variables. Okay? So we're going to see in the next couple of lectures, you know, different modeling techniques for constraint programming, and also different techniques for actually pruning the search base. Okay? See you next time.