1 00:00:00,440 --> 00:00:03,940 Okay, this is discrete optimization constraint programming part two. 2 00:00:03,940 --> 00:00:06,740 Okay, so this is the goal of the lectures, of the lecture. 3 00:00:06,740 --> 00:00:10,940 Okay, so we're going to illustrate more complex constraint propagation. 4 00:00:10,940 --> 00:00:14,783 And the underlying topic is the fact that every one of the constraints in a 5 00:00:14,783 --> 00:00:19,670 constraint programming system has a dedicated algorithm, okay? 6 00:00:19,670 --> 00:00:22,230 So that's, so basically, that's the technical part, okay? 7 00:00:22,230 --> 00:00:24,885 So what are we going to do from a non technical standpoint, is that, for the 8 00:00:24,885 --> 00:00:27,855 first time, you're going to see a complex propagation algorithm if you have never 9 00:00:27,855 --> 00:00:31,806 seen any. And it's kind of amazing how, how these 10 00:00:31,806 --> 00:00:34,800 things are working. The kind of information that you are 11 00:00:34,800 --> 00:00:36,881 deducing. It's, like, you know, the first time you 12 00:00:36,881 --> 00:00:39,820 see this, it's like, wow, this program is actually pretty bright, okay? 13 00:00:39,820 --> 00:00:42,711 Of course, it's not, but, anyway, so it's going to give you a sense of what a 14 00:00:42,711 --> 00:00:45,600 constraint propagation algorithm is doing. 15 00:00:45,600 --> 00:00:48,468 It's kind of interesting. Okay, so remember, in constraint 16 00:00:48,468 --> 00:00:51,130 programming is this combination of branch and prune. 17 00:00:51,130 --> 00:00:53,980 Pruning is removing value from the domain of the variables in a first 18 00:00:53,980 --> 00:00:56,860 approximation. Branching is, oh, you're stuck. 19 00:00:56,860 --> 00:00:59,904 There is no propagation. You decide whether, you know, you assign 20 00:00:59,904 --> 00:01:01,938 a value. You decide to split the problems into 21 00:01:01,938 --> 00:01:04,270 sub-problems. Typically, you take a values and you 22 00:01:04,270 --> 00:01:08,050 start giving all kinds of values for it. You know, in turn. 23 00:01:08,050 --> 00:01:10,135 Okay? and then obviously, you know, once you 24 00:01:10,135 --> 00:01:13,096 branch you apply the constraint propagation algorithm to prune the search 25 00:01:13,096 --> 00:01:16,367 space again. Now, pruning is basically, as I told you, 26 00:01:16,367 --> 00:01:19,469 you are using the constraints while, you know, removing as many values from the 27 00:01:19,469 --> 00:01:23,720 domain of as many variables as possible. Okay? 28 00:01:23,720 --> 00:01:26,794 Branching is, you know, in, in our first approximation we'll see most 29 00:01:26,794 --> 00:01:30,027 sophisticated branches came later on, later on, but essentially trying 30 00:01:30,027 --> 00:01:34,522 possible, you know, trying possible values for the variables. 31 00:01:34,522 --> 00:01:36,920 Okay? Remember with this beautiful separation 32 00:01:36,920 --> 00:01:41,590 between the search engine and the, the constraint, the constraint store. 33 00:01:41,590 --> 00:01:43,194 Okay? And so what is happening is this guy is 34 00:01:43,194 --> 00:01:46,180 basically trying to see if the constraint is satisfiable. 35 00:01:46,180 --> 00:01:49,480 And when it, when it tries to derive as much information as it can. 36 00:01:49,480 --> 00:01:52,100 The search will make a choice and send a new constraint. 37 00:01:52,100 --> 00:01:54,350 And the constraint store is to be able to say yes or no. 38 00:01:54,350 --> 00:01:57,119 Okay? Am I still feasible, okay, or not? 39 00:01:57,119 --> 00:01:59,860 Am I infeasible, or am I infeasible, okay? 40 00:01:59,860 --> 00:02:03,124 And if it's feasible, if you believe it's feasible, you're going to say yeah, it's 41 00:02:03,124 --> 00:02:06,370 fine, you know, as far as I can tell I'm feasible. 42 00:02:06,370 --> 00:02:09,250 And sometimes, you know, you add a new constraint and then the system will say 43 00:02:09,250 --> 00:02:12,401 oh, no, no, I'm infeasble. You know, remove that choice, give me 44 00:02:12,401 --> 00:02:14,180 another choice. Okay. 45 00:02:14,180 --> 00:02:17,770 So that's basically the essence of, of constraint programming. 46 00:02:17,770 --> 00:02:21,100 The inside of this constraint store is very interesting. 47 00:02:21,100 --> 00:02:22,996 All right. So you have the domain store here, which 48 00:02:22,996 --> 00:02:26,475 is basically capturing the search space, typically associated domains to every one 49 00:02:26,475 --> 00:02:30,373 of the variables. And then gravitating around it are the, 50 00:02:30,373 --> 00:02:32,380 all these constraints. Okay? 51 00:02:32,380 --> 00:02:34,660 And they don't know about each other, and that's the key point. 52 00:02:34,660 --> 00:02:36,668 Okay? And these constraints have two goals in 53 00:02:36,668 --> 00:02:38,720 life. I told you they basically are asking 54 00:02:38,720 --> 00:02:42,618 themselves, oh, am I feasible with respect to this field of, of domains? 55 00:02:42,618 --> 00:02:45,642 So can I find an assignment for the variables using these domains such that, 56 00:02:45,642 --> 00:02:49,010 you know, I'm, you know, this constraint is satisfied? 57 00:02:49,010 --> 00:02:51,971 And then they will say, oh, but can I actually knock down some values in these 58 00:02:51,971 --> 00:02:55,170 domains, such that I reduce the search space, okay. 59 00:02:55,170 --> 00:02:58,002 And of course, as soon as you do that, some of the constraints may become 60 00:02:58,002 --> 00:03:01,026 infeasible, or some of the constraints may be able to knock down more values 61 00:03:01,026 --> 00:03:04,911 from these domains. And that's the constraint propagation 62 00:03:04,911 --> 00:03:07,370 algorithm, okay. Right, the constraint does two things. 63 00:03:07,370 --> 00:03:10,442 Feasibility checking, you know, is it still feasible in the set, we're given 64 00:03:10,442 --> 00:03:13,902 the set of domains. And then pruning, given a set of domains, 65 00:03:13,902 --> 00:03:17,550 can I knock down some value for the domains of the other variables. 66 00:03:17,550 --> 00:03:21,070 Okay, now the key point, and this is one of the topic, one of the topics covered 67 00:03:21,070 --> 00:03:24,370 today, is that every one of the constraints in a constraint programming 68 00:03:24,370 --> 00:03:29,160 system, has a dedicated algorithm to do, these two tasks. 69 00:03:29,160 --> 00:03:31,211 Okay? It's going to test feasibility, using the 70 00:03:31,211 --> 00:03:33,984 semantics, the structural the constraints, and it's going to do pruning 71 00:03:33,984 --> 00:03:36,990 using the same information. Okay. 72 00:03:36,990 --> 00:03:39,679 So we, so this is the strength of constraint programming. 73 00:03:39,679 --> 00:03:42,640 You can, can explore the structure of these constraints to prune the search 74 00:03:42,640 --> 00:03:45,546 base as best as it can. So I'm going to use a very simple 75 00:03:45,546 --> 00:03:48,981 example, send more money. The story here is that, you know, this is 76 00:03:48,981 --> 00:03:52,270 a graduate student going to going to school. 77 00:03:52,270 --> 00:03:55,808 You know, he needs more money, so his father is very, and his mother is very 78 00:03:55,808 --> 00:04:00,290 reluctant to actually give him money. And so every time he asks for money he 79 00:04:00,290 --> 00:04:04,091 has to find a clever way of asking. And so here he's sent, you know, his 80 00:04:04,091 --> 00:04:07,276 parents a puzzle and that puzzle is, you know, if the parents solve the puzzle, 81 00:04:07,276 --> 00:04:11,610 they will know how much money the graduate student wants, okay? 82 00:04:11,610 --> 00:04:14,670 So that's the story. So, essentially the person has, you know, 83 00:04:14,670 --> 00:04:18,190 three words, send more money, okay, all right? 84 00:04:18,190 --> 00:04:21,494 And the amount of money has to be essentially the value of these letters 85 00:04:21,494 --> 00:04:24,515 over there. And you have to make sure, of course, 86 00:04:24,515 --> 00:04:28,660 that the addition here is valid, okay? So in a sense you have to assign 87 00:04:28,660 --> 00:04:32,300 different digits to all these letters, such that addition is valid. 88 00:04:32,300 --> 00:04:35,300 And then you will have, you know, essentially the amount that needs to be 89 00:04:35,300 --> 00:04:36,690 sent. Okay? 90 00:04:36,690 --> 00:04:39,758 So, now I'm going to show one model, okay, for solving this puzzle using 91 00:04:39,758 --> 00:04:43,351 constraint programming. It's not a good model, okay, but it's, 92 00:04:43,351 --> 00:04:47,880 it's just, you know, a model for illustrating constraint propagation. 93 00:04:47,880 --> 00:04:50,747 So, big disclaimer in many of the, many of the examples that I'm going to use, 94 00:04:50,747 --> 00:04:53,708 the entire, you know, class, is that there are many, many models that should 95 00:04:53,708 --> 00:04:57,215 be better than the ones that I'm proposing. 96 00:04:57,215 --> 00:05:00,185 They are typically chosen to illustrate different principles. 97 00:05:00,185 --> 00:05:04,029 Okay, so this a model like we would do in kindergarten, in the sense that I'm 98 00:05:04,029 --> 00:05:07,749 going to do, you know, column-wise, you know, digit-wise addition and use 99 00:05:07,749 --> 00:05:10,900 carries. Okay. 100 00:05:10,900 --> 00:05:15,640 So when you look at this thing here, okay, so you can see that you know, I'm 101 00:05:15,640 --> 00:05:21,820 going to start with the value d and e and summing to y. 102 00:05:21,820 --> 00:05:24,430 Okay? I'm going to get a carry c 1. 103 00:05:24,430 --> 00:05:26,502 Okay? And that carry is basically going to, you 104 00:05:26,502 --> 00:05:29,840 know, be used for the second, for the second column. 105 00:05:29,840 --> 00:05:33,720 And then, I'm going to generate another carry for the subsequent one and so on. 106 00:05:33,720 --> 00:05:35,634 Okay? So, in a sense, the decision variables 107 00:05:35,634 --> 00:05:39,620 here are going to be of two types. They are going to be the letters, okay 108 00:05:39,620 --> 00:05:42,670 the initial letters of the puzzle, and then they're going to be the carries, 109 00:05:42,670 --> 00:05:45,338 okay? And the letters can take the value 110 00:05:45,338 --> 00:05:49,624 between 0 and 9, they are digits, okay? And the carries of course will take the 111 00:05:49,624 --> 00:05:53,275 value 0 and 1, okay? So, that's the basic principle here. 112 00:05:53,275 --> 00:05:56,270 Okay? And so this is one of the models, okay, 113 00:05:56,270 --> 00:05:59,907 that, that, that you could write. I told you this is not the best model 114 00:05:59,907 --> 00:06:02,616 that you could write, but this is the model that will illustrate constraint 115 00:06:02,616 --> 00:06:06,029 propagation nicely. Okay, so what you see at the top over 116 00:06:06,029 --> 00:06:11,110 there, okay, so these are basically all the letters that you have, okay. 117 00:06:11,110 --> 00:06:14,945 So so, so in this particular case you have you know, the letter s, the letter 118 00:06:14,945 --> 00:06:19,430 e, the letter, you know, n, and so on and so forth. 119 00:06:19,430 --> 00:06:22,480 You have them arranged for the digit between 0 and 9. 120 00:06:22,480 --> 00:06:24,730 And then you have the two sets of these different variables. 121 00:06:24,730 --> 00:06:27,817 Okay, so you see that this is a variable value for every one of these letters, 122 00:06:27,817 --> 00:06:31,530 okay, which have to be digits, okay, between 0 and 9. 123 00:06:31,530 --> 00:06:34,602 Okay, so for every one of these letters that you see at the top, you will assign 124 00:06:34,602 --> 00:06:36,550 a particular digit. Okay? 125 00:06:36,550 --> 00:06:38,730 And then you have the carries. There are four of them. 126 00:06:38,730 --> 00:06:41,810 And the value of them, for the carries is 0 or 1. 127 00:06:41,810 --> 00:06:44,540 And then what you see here are the constraints for the problems, okay? 128 00:06:44,540 --> 00:06:48,236 So the first ones are basically telling you that all the letters have to be given 129 00:06:48,236 --> 00:06:51,779 a different digit, okay? So this is like you know in the map 130 00:06:51,779 --> 00:06:54,460 coloring or in the, in the Queens problem, okay? 131 00:06:54,460 --> 00:06:57,460 Basically not equal constraint between all the variables. 132 00:06:57,460 --> 00:07:01,580 Then you see that the value for s and for n have to be different from 0. 133 00:07:01,580 --> 00:07:04,940 These are the most significant digits of these two numbers. 134 00:07:04,940 --> 00:07:08,660 You want them to be different from 0. Then you have the value that the carry 135 00:07:08,660 --> 00:07:13,125 for the last carry has to be equal to m. When you actually look at this particular 136 00:07:13,125 --> 00:07:16,379 equation. Okay, so this is the last column. 137 00:07:17,880 --> 00:07:21,660 And then, and then, essentially you have all the other constraints that are 138 00:07:21,660 --> 00:07:27,378 looking at every one of the column and putting and, and expressing the addition. 139 00:07:27,378 --> 00:07:30,642 And it's always, in general, it's always one carry plus, you know, a couple of a 140 00:07:30,642 --> 00:07:33,684 couple of digits, okay, for, for the letters. 141 00:07:33,684 --> 00:07:36,730 And then on the other side you will have one other digit. 142 00:07:36,730 --> 00:07:39,092 And you will have essentially 10 times the carry. 143 00:07:39,092 --> 00:07:41,880 And that's what you see for every one of these constraints. 144 00:07:41,880 --> 00:07:45,255 So you always see the ten times the carry at the end of the equation. 145 00:07:45,255 --> 00:07:47,720 Okay? So that's essentially the model here. 146 00:07:47,720 --> 00:07:49,856 Okay? So it's a set of not equal constraints, 147 00:07:49,856 --> 00:07:52,877 an equation, and then a set of other equations carrying you know the, 148 00:07:52,877 --> 00:07:57,690 basically, every one of the addition for every one of these columns. 149 00:07:57,690 --> 00:07:59,730 Okay? So this is the search space. 150 00:07:59,730 --> 00:08:01,690 Okay? So the search space, initially, what you 151 00:08:01,690 --> 00:08:06,123 see there are all the digit values, okay, and you see all the letters over here. 152 00:08:06,123 --> 00:08:10,450 You see also the carries there, and these carries can take only the values 0 and 1. 153 00:08:10,450 --> 00:08:13,073 Okay, and once again, you know the key point here is that we are going to knock 154 00:08:13,073 --> 00:08:16,870 down many, many, many values from this search page, and that's the goal. 155 00:08:16,870 --> 00:08:19,492 And in this particular case, there are two things that are going to be 156 00:08:19,492 --> 00:08:22,088 interesting. It's how much we prune, okay, using 157 00:08:22,088 --> 00:08:25,148 these, these constraints. And it's also the constraint propagation 158 00:08:25,148 --> 00:08:26,768 itself. We're going to do something with one 159 00:08:26,768 --> 00:08:28,892 constraint that are going to wake up another one which is going to propagate 160 00:08:28,892 --> 00:08:32,220 again and so on and so forth. And that's this kind of propagation which 161 00:08:32,220 --> 00:08:33,970 is interesting. And this is what we are trying to 162 00:08:33,970 --> 00:08:35,820 illustrate today. Okay. 163 00:08:35,820 --> 00:08:38,820 So, this is essentially the beginning of the, of the propagation. 164 00:08:38,820 --> 00:08:40,740 Okay. So you have the not equal constraints. 165 00:08:40,740 --> 00:08:43,764 These not equal constraints are not doing anything initially, because the variables 166 00:08:43,764 --> 00:08:47,878 have all the possible values. And then you have this interesting thing 167 00:08:47,878 --> 00:08:51,370 here that you know, basically s and m cannot be 0. 168 00:08:51,370 --> 00:08:53,632 Okay? And then that m has to be equal to a 169 00:08:53,632 --> 00:08:55,250 carry. Okay? 170 00:08:55,250 --> 00:08:57,760 So, there are a couple of interesting things are going to happen there. 171 00:08:57,760 --> 00:09:00,460 Okay? So, when you see, you know, that m that s 172 00:09:00,460 --> 00:09:05,150 cannot be 0, you're going to knock down the value 0 from s. 173 00:09:05,150 --> 00:09:09,030 When it, you know, m is not equal to 0, you just knock down the value 0 from m. 174 00:09:09,030 --> 00:09:12,812 And then you have this interesting constraint, which is basically saying 175 00:09:12,812 --> 00:09:17,640 that the carry four is equal to the digit assigned to m, okay. 176 00:09:17,640 --> 00:09:22,146 Now, the carry is 0 and 1, okay. At this point, essentially m is 1 to 9, 177 00:09:22,146 --> 00:09:25,506 so there is only one value which is common to these things, and that's and 178 00:09:25,506 --> 00:09:30,684 that's the value, and that's the value 1. So these two guys are going to be 179 00:09:30,684 --> 00:09:33,990 assigned to 1, okay? And that's what you see here. 180 00:09:33,990 --> 00:09:36,874 Immediately, the system is deducing that. Okay? 181 00:09:36,874 --> 00:09:40,160 And usually once you do that, you know m, you know every, every digit, every 182 00:09:40,160 --> 00:09:44,955 letter, of course has only one value, all the other values are ruled out. 183 00:09:44,955 --> 00:09:48,080 We also know that all the digits have to be different, okay? 184 00:09:48,080 --> 00:09:51,776 So basically these non equal constraints are going to propagate and remove the 185 00:09:51,776 --> 00:09:55,370 value one for all the other, all the other letters. 186 00:09:55,370 --> 00:09:57,524 Okay? And that's essentially the state of the 187 00:09:57,524 --> 00:10:00,926 search space after this you know, a couple, you know, this not equal and this 188 00:10:00,926 --> 00:10:05,675 equality constraint. The last equality constraint that you saw 189 00:10:05,675 --> 00:10:08,811 there, okay? So not very interesting you know, right 190 00:10:08,811 --> 00:10:11,280 now. This is mostly what we have seen before. 191 00:10:11,280 --> 00:10:15,823 So things are going to get more interesting when you see this actual 192 00:10:15,823 --> 00:10:20,599 equation over there, right? And so now, we have to find a way to 193 00:10:20,599 --> 00:10:25,400 actually process that equation, okay? So I'm here right. 194 00:10:25,400 --> 00:10:27,860 And this is the equation on top of me, okay? 195 00:10:27,860 --> 00:10:31,332 So one of the things that we're first going to do is to take this equation and 196 00:10:31,332 --> 00:10:35,460 simplify it given the current state of the search space. 197 00:10:35,460 --> 00:10:37,428 Right? So we know that m is the value 1, so when 198 00:10:37,428 --> 00:10:41,440 we see, you know, the value of m we can replace that by the value of 1. 199 00:10:41,440 --> 00:10:44,170 So the equation becomes a little bit simpler, okay? 200 00:10:44,170 --> 00:10:47,037 And now what we're going to compute is, we're going to, to make sure that this 201 00:10:47,037 --> 00:10:49,951 constraint can be satisfied, we're going to compute the value, the, the, the 202 00:10:49,951 --> 00:10:52,583 set of values at the left of the equations and the set of values at the 203 00:10:52,583 --> 00:10:56,560 right of the equation. Okay? 204 00:10:56,560 --> 00:10:59,776 And obviously, these, you know there has to be a non-empty intersection between 205 00:10:59,776 --> 00:11:01,790 these two things. Okay? 206 00:11:01,790 --> 00:11:05,448 So, we're going to compute the range of, of the left, and the range of the right 207 00:11:05,448 --> 00:11:11,140 of the equation, okay. So the range of the left is 3, 11, okay. 208 00:11:11,140 --> 00:11:14,140 And I want to go slowly and tell you how we get that, because this is kind of 209 00:11:14,140 --> 00:11:17,806 interesting, okay. So, we have to, so this is essentially 210 00:11:17,806 --> 00:11:21,044 how you compute it, okay. And every one of these values that you 211 00:11:21,044 --> 00:11:24,570 see there is computed in a very systematic fashion, okay. 212 00:11:24,570 --> 00:11:29,982 So, look, the 0, which comes here, okay, the 0 is from there, comes from the value 213 00:11:29,982 --> 00:11:37,032 of the carry, of carry of the carry 3. So we have two possible values for carry 214 00:11:37,032 --> 00:11:40,586 3, 0, and 1, okay? Now if we try to bounce, you know, to 215 00:11:40,586 --> 00:11:45,002 have the smallest possible value for this left turn, we take the smallest value for 216 00:11:45,002 --> 00:11:49,972 carry 3 and that's 0. And that is the 0 that you see there. 217 00:11:49,972 --> 00:11:52,310 Okay? So the value 2 there is the same thing 218 00:11:52,310 --> 00:11:53,590 for s. Okay? 219 00:11:53,590 --> 00:11:56,534 So we look at, what is the smallest value that s can take and that is what you see 220 00:11:56,534 --> 00:12:00,100 over there. And then usually we get the 1 that is the 221 00:12:00,100 --> 00:12:03,105 value of m that, you know, that is already fixed. 222 00:12:03,105 --> 00:12:05,614 Okay? And so this is the lower bound on the 223 00:12:05,614 --> 00:12:09,660 value of this expression in the current search space. 224 00:12:09,660 --> 00:12:11,900 Now, we do the same thing for the upper bounds. 225 00:12:11,900 --> 00:12:14,360 And in the upper bound, what you are trying to do is to find a maximum value 226 00:12:14,360 --> 00:12:16,310 for that term. Okay? 227 00:12:16,310 --> 00:12:20,086 So when we see a variable like this carry three, we take the largest value, and 228 00:12:20,086 --> 00:12:23,400 this particle case, it's 1. Okay? 229 00:12:23,400 --> 00:12:26,720 then we do the same thing for, the value of s. 230 00:12:26,720 --> 00:12:29,220 which is, which is nine. Okay? 231 00:12:29,220 --> 00:12:32,360 And that is the value that you see there. the value that you see there. 232 00:12:32,360 --> 00:12:34,180 Okay. So that's a value of 9. 233 00:12:34,180 --> 00:12:37,050 And then we also have the 1 which comes from the value of m. 234 00:12:37,050 --> 00:12:40,660 Okay, and that's how you get 3 to 11, okay. 235 00:12:40,660 --> 00:12:43,604 And we can do that, and we can do that for the others, right, which is basically 236 00:12:43,604 --> 00:12:47,072 giving us 10 to 19. I won't go into details, I won't bore you 237 00:12:47,072 --> 00:12:50,474 into the details, but at this point, essentially, I know what is the range of 238 00:12:50,474 --> 00:12:54,820 the left side. I know what is the range the right side. 239 00:12:54,820 --> 00:12:58,276 Now, to have a solution to these constraints, the intersections between 240 00:12:58,276 --> 00:13:01,624 these left and the range of the left and the range of the right side have to be 241 00:13:01,624 --> 00:13:05,654 non empty. And so this is what I'm computing here. 242 00:13:05,654 --> 00:13:09,932 I'm basically looking at these two ranges, and taking the intersection. 243 00:13:09,932 --> 00:13:14,157 And the intersection has to be, you know, 10, 10, 10 and 10 to 11, okay? 244 00:13:14,157 --> 00:13:17,927 So now, I know that this intersection is not empty, so at this point, you know, I 245 00:13:17,927 --> 00:13:23,210 believe that there is a solution, okay. So I also know more information. 246 00:13:23,210 --> 00:13:26,890 I know that this term here has to range between 10 and 11. 247 00:13:26,890 --> 00:13:29,560 If I have a solution. And same thing of course, for the other 248 00:13:29,560 --> 00:13:31,610 term. So I'm going to use that information to 249 00:13:31,610 --> 00:13:33,670 start pruning the search space. Okay? 250 00:13:33,670 --> 00:13:37,149 So what I know is that, if I take the left term, okay? 251 00:13:37,149 --> 00:13:40,630 I know that it has to range between 10 and 11, okay? 252 00:13:40,630 --> 00:13:43,906 And now, I'm trying to say, oh, but how can I prune the search base using that, 253 00:13:43,906 --> 00:13:47,120 okay? So let's, you know, remove all the mass. 254 00:13:47,120 --> 00:13:49,100 And now I have just this equation there, okay? 255 00:13:49,100 --> 00:13:52,272 And I see that, you know, 10 has to be smaller or equal to the carry 3 plus the 256 00:13:52,272 --> 00:13:56,570 value of s plus 1. And that is to be smaller or equal to 11, 257 00:13:56,570 --> 00:13:58,960 okay? Now, let's assume that I'm trying to 258 00:13:58,960 --> 00:14:01,950 prune, you know, to prune the value of s. What can I do? 259 00:14:01,950 --> 00:14:05,070 Well I can first you know, take the 1 which is in the equation and move it on 260 00:14:05,070 --> 00:14:09,308 the right and the left-hand side. And then I have to say, oh, I have to 261 00:14:09,308 --> 00:14:13,217 remove this carry 3, right? So I'm going to push carry 3 on the left 262 00:14:13,217 --> 00:14:18,072 and a carry 3 on the right as well. And so now, the value of s can be bounded 263 00:14:18,072 --> 00:14:21,250 by these two expressions that you see there, right? 264 00:14:21,250 --> 00:14:24,165 And so what I have to do now, is once again, you know, I want to be very 265 00:14:24,165 --> 00:14:28,598 conservative here, right? So I want to see what is the smallest 266 00:14:28,598 --> 00:14:32,860 value that s can take, okay? And I also want to see, but what is the 267 00:14:32,860 --> 00:14:36,994 largest value that s can take? So when I evaluate this expression, I 268 00:14:36,994 --> 00:14:40,234 have to find a way to find the smallest possible value, because if I'm not 269 00:14:40,234 --> 00:14:44,890 conservative, I can prune solutions that, I can prune solutions. 270 00:14:44,890 --> 00:14:47,805 And the only thing that I want to do is prune values which appear in no 271 00:14:47,805 --> 00:14:49,490 solutions. Okay? 272 00:14:49,490 --> 00:14:52,900 So what I'm going to do here is to look and say, okay, the left-hand side, okay, 273 00:14:52,900 --> 00:14:56,780 has to be made as small as possible. How do I do that? 274 00:14:56,780 --> 00:15:00,810 Well I have a minus you know, carry 3. So I have to make this, this carry 3 as 275 00:15:00,810 --> 00:15:04,428 large as possible, because if it's large then I subtract a lot of values, and that 276 00:15:04,428 --> 00:15:07,890 value becomes very small. Okay? 277 00:15:07,890 --> 00:15:10,180 So how do I make carry 3 as large as possible? 278 00:15:10,180 --> 00:15:13,956 I take the value 1 for that, okay. And I take the value 0 to make it as 279 00:15:13,956 --> 00:15:18,308 small as possible, such that I have the largest term on, on, on the right of the 280 00:15:18,308 --> 00:15:24,078 equations. So essentially what I get there is that 281 00:15:24,078 --> 00:15:28,218 the value of s has to be essentially a greater or equal to 8, and smaller or 282 00:15:28,218 --> 00:15:32,208 equal to 10. So this interesting, right? 283 00:15:32,208 --> 00:15:36,210 So because at this point I can prune the search base dramatically for s, right? 284 00:15:36,210 --> 00:15:39,360 So I remove all these values up to 8 and 9, okay? 285 00:15:39,360 --> 00:15:42,069 And this is what this equation has told you, and I have only looked at one side 286 00:15:42,069 --> 00:15:46,550 of this equation, essentially, right? So if I look at the other side, okay? 287 00:15:46,550 --> 00:15:50,952 I know, you know, I have to make sure that this side, now, also range between 288 00:15:50,952 --> 00:15:54,958 10 and 11, okay? And so, so I can do exactly the same 289 00:15:54,958 --> 00:15:58,230 reasoning, okay? So I take these two things, I put them 290 00:15:58,230 --> 00:16:01,140 there. And assume that I'm interested here in 291 00:16:01,140 --> 00:16:05,010 looking I know already that the carry 4 is equal to 1. 292 00:16:05,010 --> 00:16:07,330 So I get this expression here. Okay? 293 00:16:07,330 --> 00:16:12,230 And then I can prove the value of, of o at this point, okay? 294 00:16:12,230 --> 00:16:16,900 And basically, it becomes the, you know o is to be basically, between 0 and 1. 295 00:16:16,900 --> 00:16:20,230 And I can, in one step, prune a lot of value for o as well. 296 00:16:20,230 --> 00:16:22,322 Okay? So all these values here you know, for 297 00:16:22,322 --> 00:16:25,441 letter o have been removed. At that point, there is only one left, 298 00:16:25,441 --> 00:16:29,352 which is 0, so I'm going to assign it. As soon as I assign it, all the not equal 299 00:16:29,352 --> 00:16:32,616 constraints, you know linked to that variable are going to stop because now 300 00:16:32,616 --> 00:16:37,026 that variable is only one value. That's when this pr, you know, this, 301 00:16:37,026 --> 00:16:40,890 this, these contraints are propagating. Remember last lecture, okay. 302 00:16:40,890 --> 00:16:43,940 And so, in a sense, all the other values, all the other variables there are 303 00:16:43,940 --> 00:16:48,150 going to propagate there, using these not equal constraints, okay. 304 00:16:48,150 --> 00:16:50,660 So, that's what you see there. Okay, so we go back to these constraints 305 00:16:50,660 --> 00:16:54,400 there, propagate them, and now the search space has been reduced. 306 00:16:54,400 --> 00:16:57,715 And the only variable, the only digit, the only letters that can take the value 307 00:16:57,715 --> 00:17:01,334 0 is o, okay. So that's, so what we have done so far is 308 00:17:01,334 --> 00:17:05,650 propagating all the constraints up to the one which is highlighted there. 309 00:17:05,650 --> 00:17:08,770 Okay, so we propagated the non-equality, the very simple equality, the first 310 00:17:08,770 --> 00:17:12,120 equation, and we are looking at the second one now, okay. 311 00:17:12,120 --> 00:17:15,820 Second one is exactly the same reasoning. As I have shown you. 312 00:17:15,820 --> 00:17:18,100 We are looking at these equations like that, and we are going to do the bound 313 00:17:18,100 --> 00:17:20,450 reasoning that I've shown you. Right? 314 00:17:20,450 --> 00:17:22,900 We simplify it a little bit using the value of the variable. 315 00:17:22,900 --> 00:17:25,290 We know that this guy is between 2 and 10. 316 00:17:25,290 --> 00:17:27,158 Okay? If this guy is between 2 and 10, we know 317 00:17:27,158 --> 00:17:31,390 that this guy, to satisfy the constraints, has to be between 2 and 10. 318 00:17:31,390 --> 00:17:33,441 And that's what we are looking at. Okay? 319 00:17:33,441 --> 00:17:37,228 So now we know the value of n. Okay, plus 10 times the carry 3 has to be 320 00:17:37,228 --> 00:17:39,299 between 2 and 10. Okay? 321 00:17:39,299 --> 00:17:42,540 So let's assume that we are interested in carry 3. 322 00:17:42,540 --> 00:17:45,285 If we are interested in carry 3, we have to take this value of n and move it on 323 00:17:45,285 --> 00:17:49,970 the left and the right, okay. So that's what we do, okay? 324 00:17:49,970 --> 00:17:53,249 And this is what we get. We get 10 time carry 3 there, okay? 325 00:17:53,249 --> 00:17:56,840 And then you have the value On the left and the value on the right for the lower 326 00:17:56,840 --> 00:18:00,730 and upper bound, okay? Now you look at this 10 times carry 3, so 327 00:18:00,730 --> 00:18:03,830 once again we have to make this guy as small as possible and this guy as large 328 00:18:03,830 --> 00:18:09,354 as possible to be conservative right? Okay, so to make this guy as small as 329 00:18:09,354 --> 00:18:12,956 possible, what do we do? We take the largest value for n, what is 330 00:18:12,956 --> 00:18:15,710 the largest value for n? It's 9, okay? 331 00:18:15,710 --> 00:18:20,524 So and, the other side, the upper bound, we have to make it as large as possible. 332 00:18:20,524 --> 00:18:24,241 And so, since this value's negated, we have to make it as small as possible so 333 00:18:24,241 --> 00:18:27,040 we will take the value 2. Okay? 334 00:18:27,040 --> 00:18:31,200 So at this point, we simplified the equation, okay, which becomes, you know, 335 00:18:31,200 --> 00:18:36,259 -7 is smaller equal to 10 times carry 3, smaller or equal to 8. 336 00:18:36,259 --> 00:18:39,523 The left side is boring, okay, so the right side is more interesting, because 337 00:18:39,523 --> 00:18:42,490 its fourth is carry 3 to be equal to what? 338 00:18:42,490 --> 00:18:44,380 To be equal to 0. Okay? 339 00:18:44,380 --> 00:18:47,700 So, this guy is not going to be 1, it's going to be 0. 340 00:18:47,700 --> 00:18:49,820 And now, something really interesting happens. 341 00:18:49,820 --> 00:18:52,196 Right? So, what we did, what we just did now, is 342 00:18:52,196 --> 00:18:56,684 looking at this second ineq, the second equations, and we found a new value here 343 00:18:56,684 --> 00:19:01,630 for carry 3. Now, the interesting point here is that 344 00:19:01,630 --> 00:19:05,480 carry 3 is also happening in the first equation. 345 00:19:05,480 --> 00:19:10,810 So, now, we are basically saying oh, but that equation has some more information. 346 00:19:10,810 --> 00:19:13,710 So I will go back and propagate that information. 347 00:19:13,710 --> 00:19:15,936 Okay. So remember the fixed point algorithm is 348 00:19:15,936 --> 00:19:18,876 always looking at this loop, and always taking, you know, looking at the 349 00:19:18,876 --> 00:19:21,865 constraints and until you cannot propagate at anything, it's going to look 350 00:19:21,865 --> 00:19:26,430 at constraints and trying to actually propagate them again. 351 00:19:26,430 --> 00:19:30,456 Now when a value of variable like, oof, I show you here, okay, has changed, it's a 352 00:19:30,456 --> 00:19:35,790 good indication that you should actually reconsider that constraint. 353 00:19:35,790 --> 00:19:38,805 So the constrain propagation algorithm is going to take that constraint and try to 354 00:19:38,805 --> 00:19:43,130 propagate it again and try to obviously to find if its still feasible and so on. 355 00:19:43,130 --> 00:19:44,523 Okay? So we're going to go back to that 356 00:19:44,523 --> 00:19:46,547 constraint. So this is the constraint that you see 357 00:19:46,547 --> 00:19:49,040 there. [NOISE] Okay? 358 00:19:49,040 --> 00:19:51,644 And we're going to simplify it, because we have a lot more information at this 359 00:19:51,644 --> 00:19:54,659 point, right? So you see the, the value of carry 4, we 360 00:19:54,659 --> 00:19:57,780 know, we know the value of o, we know the value of n. 361 00:19:57,780 --> 00:20:01,080 And so, this constraint becomes really simple at this point. 362 00:20:01,080 --> 00:20:04,990 It becomes essentially the value of s is equal to 9, okay? 363 00:20:04,990 --> 00:20:08,840 So once again, what we can do is prune the search page, okay? 364 00:20:08,840 --> 00:20:13,040 And the remove the value 8 from the value of s, assign the value 9. 365 00:20:13,040 --> 00:20:16,236 Of course you are going to propagate all the non-equal constraints and remove all 366 00:20:16,236 --> 00:20:19,465 these values. And this is all the search space has 367 00:20:19,465 --> 00:20:22,730 removed, okay, has been pruned at this point, okay. 368 00:20:22,730 --> 00:20:26,415 So essentially what I have shown you here is all these constraints are basically 369 00:20:26,415 --> 00:20:29,720 you know, influencing every other ones. Okay? 370 00:20:29,720 --> 00:20:32,220 So, constraints are going to propagate. Okay? 371 00:20:32,220 --> 00:20:36,000 Use it's dedicated algorithm to remove value from the variables. 372 00:20:36,000 --> 00:20:38,390 Now, some of these variables appear in other constraints. 373 00:20:38,390 --> 00:20:40,930 These other constraints are going to be propagated again. 374 00:20:40,930 --> 00:20:43,950 Remove more values, which are going to propagate other constraints, and so on. 375 00:20:43,950 --> 00:20:47,313 And this fixed point algorithm is really what is the core of constraint 376 00:20:47,313 --> 00:20:50,506 programming. So you basically propagate all these 377 00:20:50,506 --> 00:20:53,420 constraints until you cannot deduce anything. 378 00:20:53,420 --> 00:20:57,010 And also, you have a dedicated algorithm for every one of these constraints. 379 00:20:57,010 --> 00:20:59,141 Okay? So, let me go into the, the, the, the, a 380 00:20:59,141 --> 00:21:04,430 little bit of the mathematical details to actually implement this. 381 00:21:04,430 --> 00:21:06,390 Which are reasonably simple here. Okay? 382 00:21:06,390 --> 00:21:09,575 So, this is essentially a cons, this is a linear inequality that I'm going to show 383 00:21:09,575 --> 00:21:12,250 you how to propagate optimally. Okay? 384 00:21:12,250 --> 00:21:16,342 So, you see that the left-hand, the left-hand side here is basically a sum of 385 00:21:16,342 --> 00:21:18,040 product. Okay? 386 00:21:18,040 --> 00:21:21,430 A, i, you know, x i. X i, a decision variable, a i is 387 00:21:21,430 --> 00:21:24,809 basically constant. So that's the left-hand side, the 388 00:21:24,809 --> 00:21:29,460 right-hand side is similar. The y's are basically decision variables, 389 00:21:29,460 --> 00:21:33,594 the b's are constant, okay? So what I'm interested in, what I'm 390 00:21:33,594 --> 00:21:38,080 interested in here is essentially propagating that constraint optimally. 391 00:21:38,080 --> 00:21:42,240 Removing as many values as I can, from the domain of the variables. 392 00:21:42,240 --> 00:21:46,429 So I'm going to assume that the domain of x i and, and y i are denoted with the 393 00:21:46,429 --> 00:21:52,270 convention that I used last time. So d x i is the domain of x i. 394 00:21:52,270 --> 00:21:57,080 And d y i, y j is the domain of y j. And now what I have to do is propagate 395 00:21:57,080 --> 00:21:59,893 using that information these constraints, okay? 396 00:21:59,893 --> 00:22:03,416 So the first thing that I have to do is to test if it's feasible, okay? 397 00:22:03,416 --> 00:22:06,723 And the feasibility test here is going to be very, very simple, right? 398 00:22:06,723 --> 00:22:09,699 So how do I make sure that I can, how do I test, you know, if this constraint is 399 00:22:09,699 --> 00:22:13,480 feasible given these domains for these variables. 400 00:22:13,480 --> 00:22:15,981 Well, what I want to do is essentially take the left-hand side and make it as 401 00:22:15,981 --> 00:22:19,532 large, as large as possible, right? And take the right-hand side, and making 402 00:22:19,532 --> 00:22:22,566 it small, as small as possible. And if, if by, if the smallest values and 403 00:22:22,566 --> 00:22:25,212 the largest values don't satisfy the constraints, I know that nothing will 404 00:22:25,212 --> 00:22:29,330 satisfy the constraints, okay? So, the feasibility test. 405 00:22:29,330 --> 00:22:32,580 Look at the left-hand side and replace every decision variable by the maximum 406 00:22:32,580 --> 00:22:35,590 value I can take. If look at the right-hand side and look 407 00:22:35,590 --> 00:22:39,300 at every decision variables, and take the smallest value that it can take. 408 00:22:39,300 --> 00:22:41,820 So that's the min in this domain and then I test. 409 00:22:41,820 --> 00:22:44,370 Now I have no decision variable left, only constant. 410 00:22:44,370 --> 00:22:48,470 And I'm basically test if this is, this, this inequality is satisfied or not. 411 00:22:48,470 --> 00:22:50,535 Okay? If it's satisfied, feasible, if it's not, 412 00:22:50,535 --> 00:22:52,480 it's infeasible. Right? 413 00:22:52,480 --> 00:22:56,440 So, now essentially, I, let's assume that it satisfies all. 414 00:22:56,440 --> 00:22:58,180 Okay? Otherwise, I can't prune. 415 00:22:58,180 --> 00:23:01,220 Right? I already pruned the note in a sense. 416 00:23:01,220 --> 00:23:04,748 And so what I'm going to assume here for pruning, is that I have two values left, 417 00:23:04,748 --> 00:23:07,680 l and r, for left and right. Okay? 418 00:23:07,680 --> 00:23:10,515 Which are basically, the l is basically denoting the largest value that the 419 00:23:10,515 --> 00:23:14,382 left-hand side can take. And r is denoting the smallest value that 420 00:23:14,382 --> 00:23:15,830 r can take. Okay? 421 00:23:15,830 --> 00:23:17,790 So I'm going to use that for the pruning algorithm. 422 00:23:17,790 --> 00:23:21,512 You remember, l is the largest value for the, for the left-hand side. 423 00:23:21,512 --> 00:23:24,109 r is the smallest value for the right-hand side. 424 00:23:24,109 --> 00:23:25,860 Okay? So then this is how I prune the search 425 00:23:25,860 --> 00:23:27,360 space. Okay? 426 00:23:27,360 --> 00:23:29,090 So I want to look at x i. Okay? 427 00:23:29,090 --> 00:23:31,380 So let's, let's look at x x i. Okay? 428 00:23:31,380 --> 00:23:36,890 So what I know is that a i x i has to be greater than what? 429 00:23:36,890 --> 00:23:40,620 So, look at this, look at the, the, the initial constraints over there. 430 00:23:40,620 --> 00:23:43,440 I'm going to look at the right, I'm going to look at the right-hand side. 431 00:23:43,440 --> 00:23:47,110 So the right-hand side is r, okay, so that's going to always be there. 432 00:23:47,110 --> 00:23:50,054 And then, what I have to do is take all the other variables here, okay, and move 433 00:23:50,054 --> 00:23:53,880 it on the other side, so this, they have the largest value there. 434 00:23:53,880 --> 00:23:57,656 And those values are essentially l, except that, I don't want to double count 435 00:23:57,656 --> 00:24:00,817 x i, right? So I have to, I have already counted 436 00:24:00,817 --> 00:24:05,040 inside, I have already counted inside l, so I have to remove it. 437 00:24:05,040 --> 00:24:09,194 I have to remove a i times the domain of times the largest value in the domain of 438 00:24:09,194 --> 00:24:13,197 x of, of the, of x i. And that's what I'm doing in this 439 00:24:13,197 --> 00:24:16,789 expression here, right? And so now, I know that, I know that this 440 00:24:16,789 --> 00:24:18,420 is valid. Okay? 441 00:24:18,420 --> 00:24:21,204 So, I know that a i xi has to be greater than that for the constraint to be 442 00:24:21,204 --> 00:24:24,526 satisfied. And that leaves me this pruning rule that 443 00:24:24,526 --> 00:24:26,050 you have here. Okay? 444 00:24:26,050 --> 00:24:32,230 So, I basically take this expression divided by by a i. 445 00:24:32,230 --> 00:24:35,585 And since I want to be conservative, I have to run, well, well, that, that, 446 00:24:35,585 --> 00:24:38,732 that's fine. So, since I'm working with integers I 447 00:24:38,732 --> 00:24:41,980 have to run up of course, if it's a fractional values. 448 00:24:41,980 --> 00:24:43,990 Okay? And this is what you see here. 449 00:24:43,990 --> 00:24:45,870 Okay? So, this is what you see here, sorry. 450 00:24:45,870 --> 00:24:49,350 so what you see there, is that I'm basically taking the seal of that 451 00:24:49,350 --> 00:24:52,000 expression over here. Okay? 452 00:24:52,000 --> 00:24:55,412 And this is how I prune. And of course, y, for y I"m going to do 453 00:24:55,412 --> 00:24:59,117 exactly the same thing, except that I"m going to do, I'm, I'm going to, I'm 454 00:24:59,117 --> 00:25:04,821 going to subtract the value of y j. And then I'm going to divide by, you 455 00:25:04,821 --> 00:25:07,601 know, b j. And then I'll, instead of taking the the, 456 00:25:07,601 --> 00:25:12,381 the ceil, I'm going to take the floor. And I'm going to basically update the 457 00:25:12,381 --> 00:25:17,099 upper bound of y j. So in a sense, so what I do is that I 458 00:25:17,099 --> 00:25:20,804 update, the lower bound of the axis, I update the higher bound, the upper bound 459 00:25:20,804 --> 00:25:24,566 of the y's, using these two very simple rules that can be computed efficiently, 460 00:25:24,566 --> 00:25:28,157 which essentially, you know, as I told you, use the largest value for the x i, 461 00:25:28,157 --> 00:25:35,888 in the domain of the x i, and the smallest value in the domain of the y i. 462 00:25:35,888 --> 00:25:38,220 Okay? So lessons from this lecture. 463 00:25:38,220 --> 00:25:41,760 First that, you know, you have a dedicated algorithm for every one of the 464 00:25:41,760 --> 00:25:45,390 constraints. The constraint propagation algorithm is 465 00:25:45,390 --> 00:25:48,462 really rich, it's going to propagate these constraints until you cannot get 466 00:25:48,462 --> 00:25:51,351 information. And so as soon as you accumulate raw 467 00:25:51,351 --> 00:25:54,634 information in one variable, it's going to propagate to another one, it can come 468 00:25:54,634 --> 00:25:57,977 back and propagate all these contracts, okay. 469 00:25:57,977 --> 00:26:01,277 And this, and in this particular case, the bound propagation algorithm is very 470 00:26:01,277 --> 00:26:04,424 easy to compute. It's basically reason about, you know, 471 00:26:04,424 --> 00:26:08,585 the, the, the upper bounds and the lower bounds on every one of the variables. 472 00:26:08,585 --> 00:26:10,800 Okay? So we're going to see in the next couple 473 00:26:10,800 --> 00:26:13,569 of lectures, you know, different modeling techniques for constraint programming, 474 00:26:13,569 --> 00:26:17,000 and also different techniques for actually pruning the search base. 475 00:26:17,000 --> 00:26:19,330 Okay? See you next time.