1 00:00:00,310 --> 00:00:03,710 So welcome back to discrete optimization, this is constraint programming, part 2 00:00:03,710 --> 00:00:06,161 three. And today, what we're going to do is look 3 00:00:06,161 --> 00:00:09,490 at the rich modeling language of constraint programming. 4 00:00:09,490 --> 00:00:13,000 One of the key aspects of constraint programming is the fact that the language 5 00:00:13,000 --> 00:00:16,186 is able to capture very complex model, very complex side constraints, 6 00:00:16,186 --> 00:00:21,290 idiosyncratic constraints. And the purpose of this lecture is to 7 00:00:21,290 --> 00:00:25,330 give you a feel on how you express this model in constraint programming. 8 00:00:25,330 --> 00:00:28,864 So, I'm going to start with a very simple example, you'll see very simple of 9 00:00:28,864 --> 00:00:32,569 examples today, but every one of them is going to illustrate some aspect of, of 10 00:00:32,569 --> 00:00:38,579 the, the richness of the, the language. So this first example is called magic 11 00:00:38,579 --> 00:00:42,096 series. And a series, you know, S zero from SN is 12 00:00:42,096 --> 00:00:47,640 magic, if element I of the series SI represents the number of occurrences of 13 00:00:47,640 --> 00:00:52,670 the value I inside S. Okay? 14 00:00:52,670 --> 00:00:55,998 So, what you see here is the array from zero to four, that's the magic series of 15 00:00:55,998 --> 00:00:59,504 size five. And what we have to do is find these 16 00:00:59,504 --> 00:01:02,665 numbers, okay? Such that the series is magic, okay, so 17 00:01:02,665 --> 00:01:08,862 can you find a magic series? Come on guys, find a magic series. 18 00:01:08,862 --> 00:01:12,676 Okay? So I'll let you think a little bit, okay? 19 00:01:12,676 --> 00:01:17,410 So this one magic series, okay? So you see two, one, two, zero, zero, 20 00:01:17,410 --> 00:01:20,030 why? Well two there for zero so that means 21 00:01:20,030 --> 00:01:24,570 that there are two occurrences of zero. You see one over there, one over there. 22 00:01:24,570 --> 00:01:27,020 One occurrences of one. This is itself, right? 23 00:01:27,020 --> 00:01:31,025 So this is a little bit self referential. And then you have a two there, which 24 00:01:31,025 --> 00:01:33,860 basically tells you that there are two occurrences of two, this one and that 25 00:01:33,860 --> 00:01:36,508 one, okay. And, of course, there are zero 26 00:01:36,508 --> 00:01:39,570 occurrences of three, zero occurrences of four, okay? 27 00:01:39,570 --> 00:01:42,972 So now what we have to do is to write a program that will find magic series up to 28 00:01:42,972 --> 00:01:47,026 a thousand or something like that. The length of the series would be a 29 00:01:47,026 --> 00:01:49,190 thousand, okay, and you can do this, okay? 30 00:01:49,190 --> 00:01:51,785 So this is a simple model, okay, for doing this. 31 00:01:51,785 --> 00:01:54,962 Okay? So, what we have there is essentially the 32 00:01:54,962 --> 00:01:58,089 size of the series, then you have a range, and here you have the decision 33 00:01:58,089 --> 00:02:01,938 variables, okay? So the decision variables you have one 34 00:02:01,938 --> 00:02:05,080 decision variable for every element in the series. 35 00:02:05,080 --> 00:02:09,436 And it denotes the occurrences of that particular element inside a series, okay? 36 00:02:09,436 --> 00:02:12,571 What you see over here are the constraints, and that's the most, most 37 00:02:12,571 --> 00:02:16,399 interesting part, okay? For every value, okay, from zero to the 38 00:02:16,399 --> 00:02:20,380 life of the series okay, so you have one of these constraints. 39 00:02:20,380 --> 00:02:25,590 And that constraint specify the number of occurrences of K inside a series, okay? 40 00:02:25,590 --> 00:02:28,995 And how do you do that? Well you have this expression here, which 41 00:02:28,995 --> 00:02:33,820 is basically summing for all I inside the series, okay, and what are we summing? 42 00:02:33,820 --> 00:02:37,525 We are summing this, you know, this constraints essentially, this condition 43 00:02:37,525 --> 00:02:41,840 which basically tests if element I of the series is equal to K. 44 00:02:41,840 --> 00:02:43,725 Okay? So, one way to think about this in a 45 00:02:43,725 --> 00:02:46,960 sense. This, this, this is the key in this 46 00:02:46,960 --> 00:02:50,095 example, so one way to think about this is assume that every one of the 47 00:02:50,095 --> 00:02:54,360 decision's variables, have already been given a value. 48 00:02:54,360 --> 00:02:59,080 What you're doing here is testing if this condition is true or false. 49 00:02:59,080 --> 00:03:00,980 Okay? If it's true, it has a value one. 50 00:03:00,980 --> 00:03:04,219 If it's false, it has the value zero. So what you are really doing here is 51 00:03:04,219 --> 00:03:08,250 summing all the constraints and finding out if they are true or false. 52 00:03:08,250 --> 00:03:11,290 And if they are true, you get a one, if they are false, you have zero. 53 00:03:11,290 --> 00:03:15,710 And that's essentially equivalent to summing the number occurrences, of key 54 00:03:15,710 --> 00:03:19,474 inside a series, okay? So what you see here is a, what is called 55 00:03:19,474 --> 00:03:23,100 a reified constraint, it's a very, very useful uh,con, concept. 56 00:03:23,100 --> 00:03:29,627 And it's basically the ability to transform a constraint into a 01 value, 57 00:03:29,627 --> 00:03:35,356 okay, a 01 variable, okay? And so as I said before, the variable is 58 00:03:35,356 --> 00:03:38,092 going to get the value one, if the constraint is true, it's going to get the 59 00:03:38,092 --> 00:03:41,818 value zero otherwise. Okay, let me, let me explain a little how 60 00:03:41,818 --> 00:03:45,322 this whole thing works. Okay so this is essentially taking the 61 00:03:45,322 --> 00:03:50,154 model and unfolding it, okay so that you see every part of the sum okay? 62 00:03:50,154 --> 00:03:53,997 So you see the series zero is what, it's the sum of series zero is equal to zero 63 00:03:53,997 --> 00:03:58,650 plus, series one is equal to zero, and so on and so forth. 64 00:03:58,650 --> 00:04:02,170 Okay, so you are testing, you know, how many of these variables have the value 65 00:04:02,170 --> 00:04:05,142 zero. Okay, for series one it's exactly the 66 00:04:05,142 --> 00:04:08,522 same thing, but now you're testing if the series one, if series zero is equal to 67 00:04:08,522 --> 00:04:13,800 one, if series one is equal to one, if series two is equal to one and so on. 68 00:04:13,800 --> 00:04:16,178 Okay? And so you basically have this big system 69 00:04:16,178 --> 00:04:19,480 here of constraints. Every one of these sub-constraints here, 70 00:04:19,480 --> 00:04:22,504 every one of these constraints is, consists of many, many sub-constraints 71 00:04:22,504 --> 00:04:25,385 that you see over there. Okay? 72 00:04:25,385 --> 00:04:28,100 So, now you have to find this series, of course. 73 00:04:28,100 --> 00:04:30,600 And one of the things that we can do is start giving value, okay? 74 00:04:30,600 --> 00:04:35,540 So if you give the value one to to, to series zero, what is happening? 75 00:04:35,540 --> 00:04:38,080 Well, essentially you put a one over here, okay? 76 00:04:38,080 --> 00:04:41,724 So that's the value that you have, okay? And no of course, you know, by 77 00:04:41,724 --> 00:04:45,156 definitions is, if series, you know, zero is equal to one, you know that there is 78 00:04:45,156 --> 00:04:50,426 at least one occurrences of one, and that's what you see over there, okay? 79 00:04:50,426 --> 00:04:54,490 So we took the test over there, it's true now, you have this one over there. 80 00:04:54,490 --> 00:04:57,340 And of course, all the other values there, you know they are false and 81 00:04:57,340 --> 00:05:01,730 therefore you replace them by zero, okay? And so this is the new system now, once 82 00:05:01,730 --> 00:05:04,540 you have this additional piece of information. 83 00:05:04,540 --> 00:05:07,100 You simplify it the whole system of constraints. 84 00:05:07,100 --> 00:05:10,250 Every time the constraint becomes true you replace it by one, every time the 85 00:05:10,250 --> 00:05:14,280 constraint becomes false you replace it by zero, okay? 86 00:05:14,280 --> 00:05:17,544 And so now for instance at this point, you know that series one is greater than 87 00:05:17,544 --> 00:05:20,910 zero, and therefore you can look at, you know, you can look at that value and know 88 00:05:20,910 --> 00:05:25,890 that as series one is equal to zero you can remove it. 89 00:05:25,890 --> 00:05:28,420 And once again, you simplify the overall system. 90 00:05:28,420 --> 00:05:32,422 That's what's going on behind the scene, that's how the propagation works on reifi 91 00:05:32,422 --> 00:05:36,610 constraint, okay? So, what is happening behind the scene? 92 00:05:36,610 --> 00:05:41,171 This is what the system does when it has assistance, including reifi constraints. 93 00:05:41,171 --> 00:05:44,587 Essentially what it does, it replace every one of these expression by the 94 00:05:44,587 --> 00:05:48,050 booleq variables, okay? So if we have these Booleq variables that 95 00:05:48,050 --> 00:05:51,000 you see over there. And then you state constraints and these 96 00:05:51,000 --> 00:05:54,685 constraints are basically turnary constraints instead of binary constraints 97 00:05:54,685 --> 00:05:58,295 now, okay? So you have a constraint which is called 98 00:05:58,295 --> 00:06:01,760 booleq, okay? Which now takes three variables, okay? 99 00:06:01,760 --> 00:06:04,050 The Booleq variable that we just introduced. 100 00:06:04,050 --> 00:06:07,289 And then s i and k. And basically a constraints like this, 101 00:06:07,289 --> 00:06:10,479 this is a specification of the constraints, right, so bool B, X, V, 102 00:06:10,479 --> 00:06:13,688 okay? And that constraints is going to be true 103 00:06:13,688 --> 00:06:17,051 if B equal one and then X is to be equal to V, or if B equals zero, then X is to 104 00:06:17,051 --> 00:06:22,008 be different from V. So in essential what we did all, all, all 105 00:06:22,008 --> 00:06:26,038 of these reifi constraints, and replaced these by these turnery and their new 106 00:06:26,038 --> 00:06:29,643 booleq values. And when we do the sum, this is piece of 107 00:06:29,643 --> 00:06:32,854 cake, right? So the only thing that we are using here, 108 00:06:32,854 --> 00:06:37,846 are basically the booleq variables, okay? So in a sense, the beautiful model that 109 00:06:37,846 --> 00:06:41,206 I've shown you is basically automatically compiled by the system into a system like 110 00:06:41,206 --> 00:06:44,159 this. Into this model, which essentially 111 00:06:44,159 --> 00:06:47,090 doesn't reason about reifi constraints anymore. 112 00:06:47,090 --> 00:06:49,730 It reasons about natural, you know, simple constraints between booleq 113 00:06:49,730 --> 00:06:52,930 variables and other variables. Okay? 114 00:06:52,930 --> 00:06:56,550 Now, let me move to another example which is called the Stable Marriage problem. 115 00:06:56,550 --> 00:06:58,834 Okay? So, now, here I'm not going to define 116 00:06:58,834 --> 00:07:02,330 what is, I'm not going to argue what a marriage is. 117 00:07:02,330 --> 00:07:04,790 This is a scientific problem, here. Okay? 118 00:07:04,790 --> 00:07:08,330 And for the purpose of these examples, which have been defined a long time ago. 119 00:07:08,330 --> 00:07:11,424 Okay, the marriage is going to be between man and woman, okay? 120 00:07:11,424 --> 00:07:15,136 And so what we are interested in doing is essentially marrying this couple of 121 00:07:15,136 --> 00:07:18,530 beautiful people. You can see how beautiful they are right. 122 00:07:18,530 --> 00:07:25,450 And we have to marry them such that the marriage are going to be stable. 123 00:07:25,450 --> 00:07:28,805 You know once again we have a bunch of men and we have a bunch of woman, okay, 124 00:07:28,805 --> 00:07:34,020 and we have to marry them together. The input, the only inputs that we get. 125 00:07:34,020 --> 00:07:39,080 Is that for every woman is going to provide a ranking for the man okay? 126 00:07:39,080 --> 00:07:41,748 So that's what you see there and of course every man is going to do the same 127 00:07:41,748 --> 00:07:45,572 for every woman, okay? So you see there Hugh is basically 128 00:07:45,572 --> 00:07:51,895 ranking Angeline on top, and then you know Holly and the Kara, and then Julia. 129 00:07:51,895 --> 00:07:56,587 Okay, and then on the other direction you know Holly likes, you know Clive very 130 00:07:56,587 --> 00:08:00,010 much, and so on and so forth. Okay? 131 00:08:00,010 --> 00:08:02,547 So for every woman your going to get a ranking of the man, for every man your 132 00:08:02,547 --> 00:08:06,567 going to get a ranking for the woman. And now we have to make sure that these 133 00:08:06,567 --> 00:08:08,980 marriages are going to be stable. Okay? 134 00:08:08,980 --> 00:08:12,390 Now, we have absolutely no clue how to make people fall in love. 135 00:08:12,390 --> 00:08:15,240 We even have less clue to make sure that they stay in love. 136 00:08:15,240 --> 00:08:18,670 But we going to do a scientific approach to this problem, okay? 137 00:08:18,670 --> 00:08:21,596 And this is the key, okay? So these are called the stability rules 138 00:08:21,596 --> 00:08:24,539 for a marriage, okay? So, and we going to say that a marriage 139 00:08:24,539 --> 00:08:29,220 between Hugh and Angelina is stable. If two conditions are true. 140 00:08:29,220 --> 00:08:33,410 The first one, if Angelina prefer another man, let's say George, right. 141 00:08:33,410 --> 00:08:36,350 So just taking you know, completely randomly George, okay? 142 00:08:36,350 --> 00:08:41,246 So if Angelina prefer George over Hugh, then George must prefer her spouse his 143 00:08:41,246 --> 00:08:44,620 spouse, over Angelina. Okay? 144 00:08:44,620 --> 00:08:48,806 So Angelina wants to switch to George, but George say no, no, no, no I'm fine. 145 00:08:48,806 --> 00:08:51,350 You know? And so, of course you have to have the 146 00:08:51,350 --> 00:08:54,705 opposite rule right, so if you prefer another woman, let's say Julia over 147 00:08:54,705 --> 00:08:58,153 Angelina. Then Julia must prefer her spouse to, 148 00:08:58,153 --> 00:09:00,210 over Hugh. Okay? 149 00:09:00,210 --> 00:09:03,612 So in a sense what Hugh have is that you know, Hugh and Angelina may not be very 150 00:09:03,612 --> 00:09:07,220 happy, they both want to switch but they can't. 151 00:09:07,220 --> 00:09:08,430 They are stuck together. Okay? 152 00:09:08,430 --> 00:09:11,410 So that's why the marriage is stable. Okay? 153 00:09:11,410 --> 00:09:15,184 So that's what we want to do. We want to write a motor here, such that 154 00:09:15,184 --> 00:09:20,540 we design a set of stable marriage for all these Hollywood stars. 155 00:09:20,540 --> 00:09:22,740 Right? So what are the decision variables? 156 00:09:22,740 --> 00:09:24,690 Well there would be two sets of decision variables. 157 00:09:24,690 --> 00:09:28,650 There will be for every man we'll find a wife, and for every woman we'll find a 158 00:09:28,650 --> 00:09:31,255 husband. Okay, so that's going to the decision 159 00:09:31,255 --> 00:09:32,950 variable. And that's what you see at the bottom 160 00:09:32,950 --> 00:09:34,220 here. Right? 161 00:09:34,220 --> 00:09:37,996 So for every man you find a wife, which has to be of course, a woman in this 162 00:09:37,996 --> 00:09:41,474 particular case. And then for every woman, we have to find 163 00:09:41,474 --> 00:09:43,750 a husband, which is in this particular case a man. 164 00:09:43,750 --> 00:09:45,340 Okay? You have the data here. 165 00:09:45,340 --> 00:09:47,190 Okay? So you see all the men, all the women, 166 00:09:47,190 --> 00:09:50,290 you have also the preferences for the men and the women. 167 00:09:50,290 --> 00:09:53,230 Okay? So wrank of Hugh, Julia means what is the 168 00:09:53,230 --> 00:09:59,030 ranking of Julia in the ordering of Hugh? And the lower the value, the higher the 169 00:09:59,030 --> 00:10:02,950 preference. For that particular woman, okay? 170 00:10:02,950 --> 00:10:06,613 And, of course, vice versa for the men. Okay, so this is basically telling what 171 00:10:06,613 --> 00:10:10,355 is the ranking of Hugh inside for, for Julia. 172 00:10:10,355 --> 00:10:13,540 Okay? So, the first thing we have to do, and 173 00:10:13,540 --> 00:10:18,297 this actually very, very nice, is we have first to specify the rules of marriage is 174 00:10:18,297 --> 00:10:23,940 this particularly example, okay? And the way we'll do that is simply by 175 00:10:23,940 --> 00:10:27,884 specifying that you know, if I'm married to someone, that someone is to be married 176 00:10:27,884 --> 00:10:33,400 with me, and this is what these two rules here are basically saying. 177 00:10:33,400 --> 00:10:39,360 For every man, the husband of the wife of that man is to be the man itself, okay? 178 00:10:39,360 --> 00:10:42,160 And, you know, equivalently for the woman, okay? 179 00:10:42,160 --> 00:10:47,540 So the wife of the husband of a woman has to be the woman herself, okay? 180 00:10:47,540 --> 00:10:50,760 So that's the first set of rule that we have to, to express. 181 00:10:50,760 --> 00:10:53,769 And there is something really, really interesting about these, these 182 00:10:53,769 --> 00:10:57,264 constraints, right. So what you see here is that, you know, 183 00:10:57,264 --> 00:11:01,736 wife of m is a decision variable. That's a variable, and it's indexing 184 00:11:01,736 --> 00:11:04,990 husband, which is also an array of variables. 185 00:11:04,990 --> 00:11:08,610 So you have a central variable, indexing an array of variables. 186 00:11:08,610 --> 00:11:13,485 Okay, very expressive feature, of, you know, constraint programming languages. 187 00:11:13,485 --> 00:11:17,205 Okay, now the next thing an the last thing we need to do, is to actually 188 00:11:17,205 --> 00:11:21,260 state, all the stability rules of the marriage. 189 00:11:21,260 --> 00:11:23,200 An that's what you see in the last four lines here. 190 00:11:23,200 --> 00:11:25,804 Okay, so we going to take every man an every woman, an then every woman an every 191 00:11:25,804 --> 00:11:29,390 man, and we go to state of the marriage has to be stable. 192 00:11:29,390 --> 00:11:34,682 Okay, so what, oops, what you see here, is, is the first, the first stability 193 00:11:34,682 --> 00:11:36,857 rule. Okay? 194 00:11:36,857 --> 00:11:41,440 And what this means is that m prefers w over his wife. 195 00:11:41,440 --> 00:11:43,470 Okay, so that's the left part of this condition. 196 00:11:43,470 --> 00:11:47,246 Okay, left part of this condition of this simplication here Is the fact that m 197 00:11:47,246 --> 00:11:51,770 prefers w over his wife. Now, if this the case, what we have to 198 00:11:51,770 --> 00:11:58,490 make sure of, okay, is that you know, the woman prefers her husband over m, okay? 199 00:11:58,490 --> 00:12:02,420 And that's what the condition that you see here is expressing okay? 200 00:12:02,420 --> 00:12:06,452 So essentially what we have here is a condition which say, is saying that if a 201 00:12:06,452 --> 00:12:10,804 particular man prefer a particular woman over his spouse, then it must be the case 202 00:12:10,804 --> 00:12:16,500 that her woman prefers her husband over this man, okay? 203 00:12:16,500 --> 00:12:19,764 And so once again what is interesting here is two things, first it is a logical 204 00:12:19,764 --> 00:12:23,064 implication, okay? Nice, we can express all kinds of logical 205 00:12:23,064 --> 00:12:26,262 constraints in this language. The other thing that you see here which 206 00:12:26,262 --> 00:12:29,170 is very interesting. And once again, what we have here is a 207 00:12:29,170 --> 00:12:32,480 two dimensional matrix of preferences, okay? 208 00:12:32,480 --> 00:12:35,530 Matrix, you know, it's a matrix event in this particular case. 209 00:12:35,530 --> 00:12:39,362 But we index it here, okay? As you can see, by a decision variable, 210 00:12:39,362 --> 00:12:41,846 okay? So once again, a big array, big matrix 211 00:12:41,846 --> 00:12:45,070 index by a decision variable. Okay? 212 00:12:45,070 --> 00:12:48,031 So that's all we need, that's the entire model, and with that we can solve all 213 00:12:48,031 --> 00:12:50,792 Hollywood's problems. Okay? 214 00:12:50,792 --> 00:12:53,510 there are two interesting features I told you. 215 00:12:53,510 --> 00:12:56,486 The first one is called the element constraint, it's the ability to index a 216 00:12:56,486 --> 00:12:59,510 rate or a matrix with complex expressions involving variables, all single 217 00:12:59,510 --> 00:13:02,780 variables. And then we have the ability to activate 218 00:13:02,780 --> 00:13:05,315 increment logical combination of constraint. 219 00:13:05,315 --> 00:13:09,620 Okay? So, that's to address what I said to you. 220 00:13:09,620 --> 00:13:11,500 Okay? So, let me, let me go into a little bit 221 00:13:11,500 --> 00:13:15,070 of the details of these features because they are interesting. 222 00:13:15,070 --> 00:13:17,798 And what you want to understand is how actually they are used in pruning the 223 00:13:17,798 --> 00:13:19,610 search space. Okay? 224 00:13:19,610 --> 00:13:22,840 So, we're going to look at the basic, the simplest element constraints. 225 00:13:22,840 --> 00:13:25,450 Right? So, you have X and Y which are variables. 226 00:13:25,450 --> 00:13:27,020 Okay? And we have an array C. 227 00:13:27,020 --> 00:13:29,860 Okay? That array C is an array of Constantin's. 228 00:13:29,860 --> 00:13:31,382 Okay? It could be an array of variables in the 229 00:13:31,382 --> 00:13:34,115 most complex case. In this particular case, we adjust an 230 00:13:34,115 --> 00:13:36,718 array of int, okay? And then the constraint is [UNKNOWN], 231 00:13:36,718 --> 00:13:39,103 okay? So we are basically saying that C is 232 00:13:39,103 --> 00:13:42,470 equal to CY, okay? So once again, you know, this c here, 233 00:13:42,470 --> 00:13:45,809 that you see, okay, that's an array of int, okay and Y is a decision variable, 234 00:13:45,809 --> 00:13:50,350 okay, X is a decision variable as well. Okay? 235 00:13:50,350 --> 00:13:52,100 Now this is an example. Okay? 236 00:13:52,100 --> 00:13:54,600 So I'm going to, I'm going to show you the various example. 237 00:13:54,600 --> 00:13:57,687 You see X over there and the value that it can take, the, the X over there it can 238 00:13:57,687 --> 00:14:01,871 take the value between three and five. And you see Y there, which can take 239 00:14:01,871 --> 00:14:04,110 between zero and five. Okay? 240 00:14:04,110 --> 00:14:06,680 So that's the domain of these variables when we start, okay? 241 00:14:06,680 --> 00:14:09,670 So we, I, I'm going to assume that we have that, okay? 242 00:14:09,670 --> 00:14:12,571 Then you see the array C, okay? So this is the array, array at index 243 00:14:12,571 --> 00:14:15,598 zero, it has the value three. At index one, the value four, and so on 244 00:14:15,598 --> 00:14:18,780 and so forth. And at the last index five, it has the 245 00:14:18,780 --> 00:14:21,610 value three, okay? So that's what you see over there. 246 00:14:21,610 --> 00:14:23,850 Okay, now what is this constraint doing, okay? 247 00:14:23,850 --> 00:14:27,945 If I have the information that X is to be equal to X is not three, what's going to 248 00:14:27,945 --> 00:14:30,770 happen? Of course the first thing we can do is 249 00:14:30,770 --> 00:14:33,383 remove that value from the domain of the variable, okay, that's what you see over 250 00:14:33,383 --> 00:14:35,300 there. Okay? 251 00:14:35,300 --> 00:14:37,677 But can you deduce something more? Okay? 252 00:14:37,677 --> 00:14:41,211 So what we know is that what, what the constraints is going to do is look, you 253 00:14:41,211 --> 00:14:46,426 know, the constraints is x=c[y]. So we want to prevent Y from taking a 254 00:14:46,426 --> 00:14:50,200 value that's going to give three to X. Okay? 255 00:14:50,200 --> 00:14:52,562 How do we do that? Well we look at the value inside of the 256 00:14:52,562 --> 00:14:54,260 index which has a three. Okay? 257 00:14:54,260 --> 00:14:58,355 There is the first one the index zero, and there is the last one which is index 258 00:14:58,355 --> 00:15:00,080 five. Okay? 259 00:15:00,080 --> 00:15:03,984 So we can, we have to actually remove the value zero and the value five from the 260 00:15:03,984 --> 00:15:07,690 domain of one. And that's what you see there, okay? 261 00:15:07,690 --> 00:15:11,120 So we remove the value zero, we remove the value five from the domain of Y. 262 00:15:11,120 --> 00:15:14,711 So in a sense what is interesting here is that if I know some more information 263 00:15:14,711 --> 00:15:18,095 about X, I can propagate it directly on y. 264 00:15:18,095 --> 00:15:21,467 Okay? So, no, assume that I've learned 265 00:15:21,467 --> 00:15:24,820 something about Y. I've learned, for instance, that Y cannot 266 00:15:24,820 --> 00:15:26,900 be four. Okay, what's going to happen? 267 00:15:26,900 --> 00:15:29,540 Well, Y cannot be four, so what does it mean? 268 00:15:29,540 --> 00:15:33,188 It means that Y here, you know, I cannot index this array with that particular 269 00:15:33,188 --> 00:15:36,940 value. And that particular value is four, okay? 270 00:15:36,940 --> 00:15:41,840 So it basically means I removed it, okay? But nothing happens to this one, okay? 271 00:15:41,840 --> 00:15:45,622 Because the value four can also be of time if, you know, Y is taking the value 272 00:15:45,622 --> 00:15:50,420 one which is over there, okay? So, at this point I cannot remove anybody 273 00:15:50,420 --> 00:15:54,140 from X, okay? So this is essentially only removing some 274 00:15:54,140 --> 00:15:59,056 part of these array, but you know, I can still assign the value four to X. 275 00:15:59,056 --> 00:16:02,838 But if, if Y now is different from one, then I can remove this value one over 276 00:16:02,838 --> 00:16:07,316 there, okay? Please. 277 00:16:07,316 --> 00:16:10,676 Yes. And then essentially at that point, you 278 00:16:10,676 --> 00:16:14,706 can see that the only value which is left for X is the value five, and therefore X 279 00:16:14,706 --> 00:16:19,613 has to be equal to five which is what you saw, oops. 280 00:16:19,613 --> 00:16:27,505 What you saw just before, okay? So I'm running over the animation again 281 00:16:27,505 --> 00:16:30,915 to tell you that the end game here has only value which is left for X, which is 282 00:16:30,915 --> 00:16:34,359 five. And only two value which are left for Y 283 00:16:34,359 --> 00:16:37,140 which are two and three. Okay? 284 00:16:37,140 --> 00:16:40,068 So that's the element constraints. Two thing which are interesting, 285 00:16:40,068 --> 00:16:43,180 propagation goes from Y to X, and from X to Y.