1 00:00:00,380 --> 00:00:02,940 Okay guys, welcome back. So, what we have seen in the last couple 2 00:00:02,940 --> 00:00:05,865 of lectures are basically many of the tools that are offered by constraint 3 00:00:05,865 --> 00:00:09,160 programming. So, what I want to do in the next couple 4 00:00:09,160 --> 00:00:12,552 of lectures is actually tell you how you can use these tools to do interesting 5 00:00:12,552 --> 00:00:15,890 things, okay? And the first thing today is going to be 6 00:00:15,890 --> 00:00:18,984 about symmetries, okay? So a lot of problems in practice of 7 00:00:18,984 --> 00:00:23,950 natural symmetry, okay? There are things that are just the same. 8 00:00:23,950 --> 00:00:27,793 And therefore you want to actually explore that information to do search in 9 00:00:27,793 --> 00:00:31,278 a better fashion. So, essentially you want to bring this 10 00:00:31,278 --> 00:00:35,279 symmetry so that you are to get always a smaller search string, okay? 11 00:00:35,279 --> 00:00:38,854 So, so what I'm basically saying here is that there are a lot of problems, with a 12 00:00:38,854 --> 00:00:42,371 lot of symmetries. Naturally, when you express them, they 13 00:00:42,371 --> 00:00:45,474 have these symmetries. And exploring these symmetrical part of 14 00:00:45,474 --> 00:00:48,999 the search trees is completely useless. If you have explored one part and then 15 00:00:48,999 --> 00:00:51,417 you explore the part which is really symmetrical to it, it's just a waste of 16 00:00:51,417 --> 00:00:54,170 time. If there was no solution to that part, 17 00:00:54,170 --> 00:00:57,810 there will be no solution to the, to the symmetrical part, okay? 18 00:00:57,810 --> 00:01:01,254 So, there are many kinds of symmetries. In these lectures I will basically only 19 00:01:01,254 --> 00:01:05,540 talk about two of them, variable symmetries and value symmetries, okay? 20 00:01:05,540 --> 00:01:08,077 And the way we're going to break these symmetries in this lecture is using 21 00:01:08,077 --> 00:01:11,333 symmetry-breaking constraints. There are other ways to do this, but this 22 00:01:11,333 --> 00:01:14,620 is the only one thing that I want to focus, one thing at the time, okay? 23 00:01:14,620 --> 00:01:17,288 And so what I'm going to talk about is, oh, you know, we can break variable 24 00:01:17,288 --> 00:01:20,640 symmetries and how we can break you know value symmetry. 25 00:01:20,640 --> 00:01:23,190 So, once again, right, so this is an introduction. 26 00:01:23,190 --> 00:01:26,860 There are thousands of papers on this topic, okay, thousand ways of doing this. 27 00:01:26,860 --> 00:01:29,370 But I'll give you an introduction to this technique, okay?. 28 00:01:29,370 --> 00:01:32,698 So, we'll start with you know variable symmetries, and I'm going to introduce a 29 00:01:32,698 --> 00:01:36,078 very simple example, which is called Balance Incomplete Block Design, BIBDs 30 00:01:36,078 --> 00:01:40,160 for, you know, those of us who actually work on this. 31 00:01:40,160 --> 00:01:45,102 So, the input is a set of five numbers that probably mean nothing to you, okay? 32 00:01:45,102 --> 00:01:48,067 So v, b, r, k, l, okay? Now forget about them, okay. 33 00:01:48,067 --> 00:01:51,469 So what we are really looking for is a matrix, okay, 0, 1 matrix that the value 34 00:01:51,469 --> 00:01:55,906 in that matrix are going to be 0, 1. So we'll have 0, 1 decision variables, in 35 00:01:55,906 --> 00:01:58,950 a sense. And the matrix of size v, v, okay, v 36 00:01:58,950 --> 00:02:03,740 rows, v columns, okay. And what we want is that this matrix 37 00:02:03,740 --> 00:02:08,465 satisfies three kinds of constraints. The first one is that the number of one 38 00:02:08,465 --> 00:02:12,570 on every row, okay, of that matrix, has to be r. 39 00:02:12,570 --> 00:02:16,340 The number of one on every column has to be k, okay? 40 00:02:16,340 --> 00:02:20,080 And then the scalar product, or every two rows, okay? 41 00:02:20,080 --> 00:02:24,230 Has to be exactly l okay? So this is for instance a simple example 42 00:02:24,230 --> 00:02:28,719 of a BIBD, okay? So this is a BIBD which has a value 3, 3, 43 00:02:28,719 --> 00:02:32,690 2, 2, 1, okay? 3, 3, 2, 2, 1, okay? 44 00:02:34,830 --> 00:02:37,530 So that means that it has three rows, okay, we can see that, you have three 45 00:02:37,530 --> 00:02:41,355 columns, okay? And then on every row, you see exactly 1, 46 00:02:41,355 --> 00:02:44,870 1, or, 2, 1, sorry. So that's because you have a 2 over 47 00:02:44,870 --> 00:02:47,853 there, 2, 1, okay? And on every column you have also 2, 1, 48 00:02:47,853 --> 00:02:51,363 and when you do the Cartesian product of these, of every two rows, you will have 49 00:02:51,363 --> 00:02:54,765 exactly, the value of that Cartesian product, that, that, the value of that 50 00:02:54,765 --> 00:02:59,730 scalar product, sorry, is going to be exactly 1, okay? 51 00:02:59,730 --> 00:03:02,812 Which essentially means that if you do the intersection of these guys, they have 52 00:03:02,812 --> 00:03:05,590 only one position where they intersect, okay? 53 00:03:05,590 --> 00:03:09,240 So that's, that's what we want to do. We want to find, you know, BIBDs like 54 00:03:09,240 --> 00:03:12,528 this, okay? Now this is, so why, why, why, why are we 55 00:03:12,528 --> 00:03:15,358 interested in this? And one of the reasons is that this is an 56 00:03:15,358 --> 00:03:19,250 example of combinatorial design. There are a lot of people searching for 57 00:03:19,250 --> 00:03:24,150 these kinds of things, and what they always have is a lot of symmetry. 58 00:03:24,150 --> 00:03:26,985 And I want to show you that on a bigger example after you know, showing you the 59 00:03:26,985 --> 00:03:30,330 model, okay? The model is actually very simple, right? 60 00:03:30,330 --> 00:03:32,970 We are looking for the matrix of 0, 1 variables, okay? 61 00:03:32,970 --> 00:03:36,534 So, essentially the decision variable are going to be n i j, okay, telling you what 62 00:03:36,534 --> 00:03:40,490 is the value of position i and j in the matrix. 63 00:03:40,490 --> 00:03:44,260 And then, essentially, the constraints are going to be really simple, alright? 64 00:03:44,260 --> 00:03:47,127 So, the first set of constraints are going to express the number of ones that 65 00:03:47,127 --> 00:03:51,389 you want on every row, then the number of 1's that you want on every column. 66 00:03:51,389 --> 00:03:54,444 And then the last constraint is a little bit more sophisticated, is basically 67 00:03:54,444 --> 00:03:59,296 computing the scale of product. What you see over there is basically you 68 00:03:59,296 --> 00:04:05,270 take the product of MIX and MGX, okay? So, that basically means I take row I and 69 00:04:05,270 --> 00:04:10,620 the column X, I take row J and value in column X. 70 00:04:10,620 --> 00:04:13,780 You know, I do it all logical and between the two, okay? 71 00:04:13,780 --> 00:04:17,780 And that's going to give me a 1 if both of them are 1, okay? 72 00:04:17,780 --> 00:04:20,464 And, and essentially what I want is that the sum of all these things in this 73 00:04:20,464 --> 00:04:23,150 particular case are going to be equal to l. 74 00:04:23,150 --> 00:04:27,176 I put a 1 in this example because that, you know, that was essentially the 75 00:04:27,176 --> 00:04:32,720 example that I've shown you before. So this is a bigger BIBD, okay? 76 00:04:32,720 --> 00:04:34,907 So this is seven rows, seven column, okay? 77 00:04:34,907 --> 00:04:38,391 I want three ones on every column, three ones on every, on every, on every column, 78 00:04:38,391 --> 00:04:42,390 three ones on every row. And I want once again that the scalar 79 00:04:42,390 --> 00:04:46,300 product be equal to 1, okay? Now this is a beautful solution, but now 80 00:04:46,300 --> 00:04:49,370 you're going to see all the symmetries, right? 81 00:04:49,370 --> 00:04:53,650 So, if I take, you know, these two rows and I swap them, okay? 82 00:04:53,650 --> 00:04:57,350 What do I get? I get another solution to the BIBDs, 83 00:04:57,350 --> 00:05:00,273 okay? So essentially, every time I take two of 84 00:05:00,273 --> 00:05:03,350 these row and I swap them, I still have a solution. 85 00:05:03,350 --> 00:05:06,840 Because essentially, there is nothing distinguishing these rows, okay? 86 00:05:06,840 --> 00:05:09,341 The only thing that I said about the rows is that they have to have a certain 87 00:05:09,341 --> 00:05:11,875 number of r. And then when I take two of them 88 00:05:11,875 --> 00:05:14,380 together, the scalar product should be a value, okay? 89 00:05:14,380 --> 00:05:17,880 There is nothing that tells me that row i is different from row j, okay? 90 00:05:17,880 --> 00:05:20,246 So essentially, every time I permute them, I have a solution. 91 00:05:20,246 --> 00:05:24,196 Plenty of symmetries, right? So now you look at the columns and this 92 00:05:24,196 --> 00:05:27,566 is exactly the same. There is nothing specific about column i 93 00:05:27,566 --> 00:05:31,506 and column j, right? So I can swap them and then I get another 94 00:05:31,506 --> 00:05:35,246 solution, okay? And so that's what, you know, the drawing 95 00:05:35,246 --> 00:05:39,541 here is basically showing you, okay? So, in a sense at this point, I told you 96 00:05:39,541 --> 00:05:44,320 that, you know, I can swap every column, I can swap every row. 97 00:05:44,320 --> 00:05:48,480 And so what I want is to avoid exploring all thse set of configuration. 98 00:05:48,480 --> 00:05:51,489 I want to find, you know, you know, solution without exploring them all, 99 00:05:51,489 --> 00:05:53,740 okay? Otherwise, I could try a particular 100 00:05:53,740 --> 00:05:56,556 route, and then another route, and then I could swap them and try again, and if 101 00:05:56,556 --> 00:05:59,548 there are no feasible solution for every two of them, I would essentially explore 102 00:05:59,548 --> 00:06:04,486 the search space twice, okay? So how do I break this these variable 103 00:06:04,486 --> 00:06:07,852 symmetries? So the the very very nice way of doing 104 00:06:07,852 --> 00:06:13,250 that is actually imposing an ordering of the variables, okay? 105 00:06:13,250 --> 00:06:16,544 So in this particular case so we are looking at the rows, and we want to make 106 00:06:16,544 --> 00:06:21,130 sure that the rows are essentially lexicographically ordered okay? 107 00:06:21,130 --> 00:06:24,030 We want the first row to be lexicographically smaller than the second 108 00:06:24,030 --> 00:06:26,980 one, and know that the second one is smaller than the third one, which is 109 00:06:26,980 --> 00:06:30,740 smaller than the fourth one, and so on, okay? 110 00:06:30,740 --> 00:06:34,440 So, I want to impose a lexicographic constraints on the various rows. 111 00:06:34,440 --> 00:06:36,860 What does that really mean? Okay? 112 00:06:36,860 --> 00:06:41,590 So, look at this thing, okay? So, what you see there is a and b, okay? 113 00:06:41,590 --> 00:06:44,630 Which are basically two, you know, two of the rows, okay? 114 00:06:44,630 --> 00:06:48,350 And I'm going to say that a is smaller than b, lexicograhically, if it's you 115 00:06:48,350 --> 00:06:53,894 know, more significant value is smaller. Than the most significant value of b, 116 00:06:53,894 --> 00:06:56,308 okay? So, this is the case in this particular 117 00:06:56,308 --> 00:06:59,054 example, okay? I have a 0 and a 1, which basically means 118 00:06:59,054 --> 00:07:02,529 that in this particular case, a is smaller than b, okay? 119 00:07:02,529 --> 00:07:05,701 But you know, it may be the case that if, if I had a one, it may be the case that 120 00:07:05,701 --> 00:07:10,141 these guys are actually the same. And that's you see in the next example 121 00:07:10,141 --> 00:07:12,670 here, okay? So, in this particular case, you see that 122 00:07:12,670 --> 00:07:15,640 both have a value 1, so I can decide at this point which one is lexicographically 123 00:07:15,640 --> 00:07:19,630 smaller than the other one. I move to the next element, and then I 124 00:07:19,630 --> 00:07:22,206 see a 1 and a 0, and what that means in this particular case is that a is 125 00:07:22,206 --> 00:07:25,778 actually lexicographically greater than b, okay? 126 00:07:25,778 --> 00:07:28,584 So, in this particular, so this is essentially what the lexicographical 127 00:07:28,584 --> 00:07:31,536 order is telling you. Compared to the first two, if the first, 128 00:07:31,536 --> 00:07:34,224 if the, you know, if this guy is three [INAUDIBLE] smaller than the other one, 129 00:07:34,224 --> 00:07:38,144 you know that a is smaller than b. If they are equal move to the next digit, 130 00:07:38,144 --> 00:07:40,799 if it's smaller or equal okay, it's smaller, if it greater or equal it's 131 00:07:40,799 --> 00:07:45,576 greater and so on, and so forth, okay? So that's essentially imposing a 132 00:07:45,576 --> 00:07:48,260 lexicographic constraints on these guys, okay? 133 00:07:48,260 --> 00:07:50,690 Now, in this particular case, you see these guys, okay? 134 00:07:50,690 --> 00:07:54,170 So this is what I, so this is essentially a solution. 135 00:07:54,170 --> 00:07:58,120 Now, this solution is not lexicograhically order, why? 136 00:07:58,120 --> 00:08:01,780 Because I have a 1 here, and a 0 there. I know that this guy, you know the row 137 00:08:01,780 --> 00:08:05,472 two is not lexicographically smaller than row three, okay? 138 00:08:05,472 --> 00:08:10,225 So, this is on the other side now, okay? So this is a lexicographically ordered 139 00:08:10,225 --> 00:08:13,066 solution. You see that rows, the first row, is 140 00:08:13,066 --> 00:08:16,890 lexicographically smaller than the second one, why? 141 00:08:16,890 --> 00:08:20,260 Well, look at this number, this is a 1, on top you have a 0, okay? 142 00:08:20,260 --> 00:08:22,625 You look at the next row, it's lexicographically greater than the 143 00:08:22,625 --> 00:08:26,152 previous one, you have a 0 there, oh you have a 1 and this guy is a 0. 144 00:08:26,152 --> 00:08:29,546 And so on and so forth, okay? So this is essentially a solution now 145 00:08:29,546 --> 00:08:33,202 which is lexicographically order. And that's what I want to search for, 146 00:08:33,202 --> 00:08:35,390 okay? Because I'm removing all the symmetries, 147 00:08:35,390 --> 00:08:37,650 okay? Now I can't swap these two guys, okay? 148 00:08:37,650 --> 00:08:40,790 Because this is lexicographically greater than that. 149 00:08:40,790 --> 00:08:44,143 So, I reduce the search base tremendously, okay? 150 00:08:44,143 --> 00:08:47,553 Now in this particular example, okay, so what I want to do as well is actually 151 00:08:47,553 --> 00:08:50,954 breaking all sort of column symmetries, okay? 152 00:08:50,954 --> 00:08:54,364 And actually, this is an interesting problem, because I can break both the 153 00:08:54,364 --> 00:08:58,049 vari, the rows, and the column symmetries at the same time I preserve at least one 154 00:08:58,049 --> 00:09:03,455 solution per symmetry group, okay? So that's what you see over there, okay, 155 00:09:03,455 --> 00:09:07,195 so you see that this column here, okay, is not lexicographically smaller than 156 00:09:07,195 --> 00:09:11,467 this one, okay. So, why because you see, where am I? 157 00:09:11,467 --> 00:09:14,550 So you see a 1 over there and a 0 there, okay? 158 00:09:14,550 --> 00:09:18,510 So, therefore you have to essentially order them as well. 159 00:09:18,510 --> 00:09:20,694 Now, you see there is two column there, and you see that they are 160 00:09:20,694 --> 00:09:23,090 lexicographically smaller than each other. 161 00:09:23,090 --> 00:09:26,282 Well the, the left most is lexicographically smaller than the right 162 00:09:26,282 --> 00:09:28,811 one. Okay, so in a sense what I want is to 163 00:09:28,811 --> 00:09:32,630 impose this lexicographic order on the rows and, and impose lexicographically 164 00:09:32,630 --> 00:09:36,753 order on the column. And search for the solution satisfying 165 00:09:36,753 --> 00:09:40,522 these lexicographic constraints. So essentially the only thing that I have 166 00:09:40,522 --> 00:09:43,702 to do in this model okay is basically add you know for every pair of rows, a 167 00:09:43,702 --> 00:09:47,820 lexicographically, a lexicographic constraint, okay? 168 00:09:47,820 --> 00:09:50,991 So this is a constraint taking all the elements of the row. 169 00:09:50,991 --> 00:09:55,087 You know, of 1, of, of row, of row i, and then all the late, all the, all the, all, 170 00:09:55,087 --> 00:09:59,055 all the elements of row i plus 1, and I'm basically saying that row i has to be 171 00:09:59,055 --> 00:10:04,886 lexicographically smaller than row i plus 1, okay? 172 00:10:04,886 --> 00:10:08,367 And of course I'm going to do the same for the next thing, which is row i plus 173 00:10:08,367 --> 00:10:13,883 1, has to be greater, smaller than row i plus 2 and so on and so forth, kay? 174 00:10:13,883 --> 00:10:17,718 And I do the same for the column And then essentially I have all the, all the rows 175 00:10:17,718 --> 00:10:21,460 and all the columns in a lexicographic order. 176 00:10:21,460 --> 00:10:24,724 Now, this lex, you know, constraints, is actually very efficient to implement in 177 00:10:24,724 --> 00:10:27,731 practice. You can find feasibility very fast, and 178 00:10:27,731 --> 00:10:31,350 you can prune and achieve the optimum pruning very fast. 179 00:10:31,350 --> 00:10:34,614 This is one of the interesting global constraints that we have in constraint 180 00:10:34,614 --> 00:10:37,966 programming, okay? So, that's basically you know, how we can 181 00:10:37,966 --> 00:10:41,400 break variable symmetry. A lot of the techniques for breaking 182 00:10:41,400 --> 00:10:45,310 variable symmetries are following a similar pattern, okay? 183 00:10:45,310 --> 00:10:48,775 Now I want to move now, to to value symmetries and I want to reintroduce you 184 00:10:48,775 --> 00:10:52,670 these beautiful actors. We were missing them, right? 185 00:10:52,670 --> 00:10:55,450 and so the problem is going to be different though. 186 00:10:55,450 --> 00:10:58,870 Okay, so it's going to be a scene allocation problem, and this time we, we 187 00:10:58,870 --> 00:11:02,575 don't care about marrying these guys, what we want is actually making a movie, 188 00:11:02,575 --> 00:11:06,359 okay? that's what these actors do for a living, 189 00:11:06,359 --> 00:11:09,125 right? And so this movie has a number of scene 190 00:11:09,125 --> 00:11:13,925 that it has to to, to shoot. And you know, an actor plays in some 191 00:11:13,925 --> 00:11:17,190 scenes and not in some others and things like this. 192 00:11:17,190 --> 00:11:20,774 And we have a very strong constraint which is that at most k scene can 193 00:11:20,774 --> 00:11:24,523 actually be shot on a particular day, okay? 194 00:11:24,523 --> 00:11:28,235 So, you can shoot k scene per day, not more than that, okay? 195 00:11:28,235 --> 00:11:31,895 Now every actor is paid by the day, whether he shoots one scene on that day 196 00:11:31,895 --> 00:11:35,599 of you know, k scene on that particular day. 197 00:11:35,599 --> 00:11:39,505 So as soon as the actor is on set for a particular day you have to pay his fees, 198 00:11:39,505 --> 00:11:43,285 and of course various actors have different fees, right, so that's what 199 00:11:43,285 --> 00:11:49,115 makes the problem interesting, okay? So the objective is, of course, the 200 00:11:49,115 --> 00:11:52,896 producer of this thing, you want to minimize your cost, okay. 201 00:11:52,896 --> 00:11:56,416 So you want to essentially to schedule the actors so that they don't spend too 202 00:11:56,416 --> 00:12:00,040 much time on the set. And you cluster the scenes in which they 203 00:12:00,040 --> 00:12:02,607 appear at the same time. But of course different actors are 204 00:12:02,607 --> 00:12:05,450 playing in different scenes so you have this tension, okay. 205 00:12:05,450 --> 00:12:09,600 And of course they have different fees. So how do we do that, okay? 206 00:12:09,600 --> 00:12:14,550 So I'm going to show you the model in a moment, but before that think about it. 207 00:12:14,550 --> 00:12:17,265 You know, what are the symmetries that we have in this problem? 208 00:12:17,265 --> 00:12:20,145 Okay? Obviously these actors are different, 209 00:12:20,145 --> 00:12:22,071 right? So, you know, you can't tell George 210 00:12:22,071 --> 00:12:25,820 Clooney that he's the same as Clive Owen. So it's not going to be the actors. 211 00:12:25,820 --> 00:12:29,140 So it's not going to be that. So the scene are going to be different as 212 00:12:29,140 --> 00:12:31,510 well. They will have different types of actor. 213 00:12:31,510 --> 00:12:33,690 So there is no symmetries on the scene. So what are the symmetries? 214 00:12:33,690 --> 00:12:36,668 Okay? So the symmetries are going to be on the 215 00:12:36,668 --> 00:12:40,112 days, okay? So essentially the days in which the 216 00:12:40,112 --> 00:12:44,425 scenes are going to be shot, okay. So this is the model, let me go over the 217 00:12:44,425 --> 00:12:48,380 model so that we can understand the symmetries afterwards. 218 00:12:48,380 --> 00:12:50,681 So what you have is a set of scenes, you have a set of days, you have a set of 219 00:12:50,681 --> 00:12:53,700 actors. Every actor is going to have a fee, 220 00:12:53,700 --> 00:12:57,060 that's how much you pay the actor per day, okay? 221 00:12:57,060 --> 00:13:02,260 No we also know that every scene you know we'll have a set of actors, okay? 222 00:13:02,260 --> 00:13:06,101 So that's what you see over there, okay? And then we learn also, we've got a 223 00:13:06,101 --> 00:13:09,503 computer particular value which is which are the scene in which the actor is 224 00:13:09,503 --> 00:13:13,236 actually appearing. This is going to be important, we derive 225 00:13:13,236 --> 00:13:17,780 this information from, you know, from the information we have about the scene. 226 00:13:17,780 --> 00:13:20,440 And then the recision variables, you see them there, okay? 227 00:13:20,440 --> 00:13:25,063 They basically specify for every scene, which is the day, you know, you know, for 228 00:13:25,063 --> 00:13:30,480 which, during which the scene is going to, is going to be shot, okay? 229 00:13:30,480 --> 00:13:33,253 So, essentially, for every scene, you have to find which day is going to be 230 00:13:33,253 --> 00:13:35,964 shot, okay? So, what you have there are two things, 231 00:13:35,964 --> 00:13:38,990 the objective function and then the constraints. 232 00:13:38,990 --> 00:13:42,154 The constraints is very simple, It's kind of an different constraints. 233 00:13:42,154 --> 00:13:44,720 It's the generalization of that is the cardinality constraints. 234 00:13:44,720 --> 00:13:49,610 And what it says is that, you know, If you look at the array shot, okay? 235 00:13:49,610 --> 00:13:53,306 So what we know about that array is that we want, at most, five in this particular 236 00:13:53,306 --> 00:13:56,204 case. So, so, you know every scene, you know, 237 00:13:56,204 --> 00:14:00,000 every day we'll be able to shoot essentially five scenes. 238 00:14:00,000 --> 00:14:03,560 So, every day, you know, every day, I can choose exactly five scenes. 239 00:14:03,560 --> 00:14:06,950 That's what this constraint is actually expressing. 240 00:14:06,950 --> 00:14:08,948 Now, once again, this is a very interesting constraints, global 241 00:14:08,948 --> 00:14:12,955 constraints and constraint programming. It can be, you know, tests will satisfy, 242 00:14:12,955 --> 00:14:16,080 it will be very efficiently and prune optimally. 243 00:14:16,080 --> 00:14:18,120 Now, the objective function is also very interesting. 244 00:14:18,120 --> 00:14:21,256 What you are doing is that you look at every actor, okay, you look at every day, 245 00:14:21,256 --> 00:14:24,441 and if the actor is actually shooting on that day, you would have to pay his fee, 246 00:14:24,441 --> 00:14:27,569 okay. So, you see the fee over there. 247 00:14:27,569 --> 00:14:30,737 And this expression that you see there, you know, which has the array [UNKNOWN] 248 00:14:30,737 --> 00:14:34,001 constraints, is basically looking at all the scene in which the actor is actually 249 00:14:34,001 --> 00:14:36,977 playing, and seeing if that scene is actually play on that particular day, 250 00:14:36,977 --> 00:14:40,954 okay? So for every day, every actor, you look 251 00:14:40,954 --> 00:14:44,510 if the actor is actually playing a scene on that particular day. 252 00:14:44,510 --> 00:14:47,272 And if that's the case, you have to pay the fee, okay? 253 00:14:47,272 --> 00:14:50,860 So that's essentially the model, okay? And as I told you, in this particular 254 00:14:50,860 --> 00:14:54,760 model we have no value symmetries, the days are the same. 255 00:14:54,760 --> 00:14:58,152 So in this particular model, I have't told you that Tuesday is different from 256 00:14:58,152 --> 00:15:01,491 Wednesday, for this actor, it doesn't matter, okay, Thursday is the same as 257 00:15:01,491 --> 00:15:05,466 Monday, okay? So in the sense, if I schedule, if I give 258 00:15:05,466 --> 00:15:08,646 a solution, okay? Where you know, with a bunch of scenes 259 00:15:08,646 --> 00:15:12,750 which are played on day one, and a bunch of scenes which are played on day two. 260 00:15:12,750 --> 00:15:15,980 Oops, you don't see me, right? So then essentially, you can swap these 261 00:15:15,980 --> 00:15:18,730 two things, and you still have a solution. 262 00:15:18,730 --> 00:15:22,344 So these things are completely inter, interchangeable, okay? 263 00:15:22,344 --> 00:15:25,100 So I can't distinguish them, so in a sense now I want to break these 264 00:15:25,100 --> 00:15:28,268 symmetries, okay? So I know that if I have a solution any 265 00:15:28,268 --> 00:15:31,175 permutation of the day is going to be also a solution, but I don't want to 266 00:15:31,175 --> 00:15:33,922 explore it. How am I going to do that? 267 00:15:33,922 --> 00:15:36,890 Okay. Now this is the reasoning, okay. 268 00:15:36,890 --> 00:15:41,374 So look at the first scene S1, okay? I want to schedule that scene, okay? 269 00:15:41,374 --> 00:15:44,820 I have let's say these five days, Monday to Friday. 270 00:15:44,820 --> 00:15:47,140 Which day am I going to schedule that scene? 271 00:15:47,140 --> 00:15:50,660 Okay, which day do I have to consider? Well, there is only one that I need to 272 00:15:50,660 --> 00:15:53,250 consider, right? Okay. 273 00:15:53,250 --> 00:15:55,090 So, and this is the first day, let's say day one. 274 00:15:55,090 --> 00:15:57,102 Why? Because at that point, all the days are 275 00:15:57,102 --> 00:15:59,465 the same, okay? Whether it's Monday or Tuesday or 276 00:15:59,465 --> 00:16:02,000 Wednesday, there are no difference between them. 277 00:16:02,000 --> 00:16:06,400 So the first thing, I can decide forever, that I'm going to schedule it on day one. 278 00:16:06,400 --> 00:16:10,590 It doesn't do anything okay? Now let's look at the second thing, okay? 279 00:16:10,590 --> 00:16:13,645 So the second thing, the second, let's, let's, sorry, let's look at the second 280 00:16:13,645 --> 00:16:16,378 scene, okay. The second scene, where can I schedule 281 00:16:16,378 --> 00:16:19,292 the second scene? well, I can schedule it on the first day, 282 00:16:19,292 --> 00:16:22,970 right, it's like the, the scene that I just schedule. 283 00:16:22,970 --> 00:16:25,790 And maybe that's interesting because there are a lot of common actors. 284 00:16:25,790 --> 00:16:28,518 Or I can decide to schedule it on a day where nothing is scheduled yet, okay, 285 00:16:28,518 --> 00:16:32,040 which is let's say day two, day three, day four, day five, okay. 286 00:16:32,040 --> 00:16:35,160 So they are essentially, but, but, day two, day three, day four, day five, they 287 00:16:35,160 --> 00:16:38,980 are all the same at this point. I can't distinguish them, so essentially 288 00:16:38,980 --> 00:16:42,910 the two days that I have to consider are day one and then day two, let's say. 289 00:16:42,910 --> 00:16:46,195 Only one of the other days, okay? So I have only two days okay? 290 00:16:46,195 --> 00:16:49,715 So in general, okay, so if I look at the particular scene, okay, the only thing 291 00:16:49,715 --> 00:16:52,960 that I have to do, is to look at the days in which I have already scheduled 292 00:16:52,960 --> 00:16:57,361 something, okay. Those are, those I have to consider, 293 00:16:57,361 --> 00:17:02,040 okay, and then I can choose one new day, a day when nothing is scheduled. 294 00:17:02,040 --> 00:17:05,770 And so if you do that, you remove all these values symmetries, okay? 295 00:17:05,770 --> 00:17:09,244 So, once again this is easy to do. You take the model okay, and what you do 296 00:17:09,244 --> 00:17:12,520 is you add these beautiful symmetry constraints here. 297 00:17:12,520 --> 00:17:15,154 Okay,so what do they say? They say that the scene one is to be 298 00:17:15,154 --> 00:17:17,370 schedules on day one. No brainer right? 299 00:17:17,370 --> 00:17:20,610 So we knew that there was you know absolutely no distinction between the 300 00:17:20,610 --> 00:17:24,273 various days at that point. And then the other constraints is 301 00:17:24,273 --> 00:17:27,720 basically taking all the other scenes and what is it doing? 302 00:17:27,720 --> 00:17:30,515 It's basically looking at the days which have been scheduled for the previous 303 00:17:30,515 --> 00:17:32,960 variables and then adding a new day, okay? 304 00:17:32,960 --> 00:17:36,660 So the new day that you see there, this beautiful plus one there, okay? 305 00:17:36,660 --> 00:17:40,281 So that's essentially what you're saying. You're saying that scene one is equal to 306 00:17:40,281 --> 00:17:43,706 one, and the next scene. You know let's say scene s, is to be 307 00:17:43,706 --> 00:17:47,240 smaller than, or is to be smaller than all the days that have been scheduled 308 00:17:47,240 --> 00:17:51,767 before, plus one new day. Okay, and so essentially what you're 309 00:17:51,767 --> 00:17:54,991 doing in this model is setting these constraints that are removing all the 310 00:17:54,991 --> 00:17:58,390 value symmetries. You will never explore the fact that 311 00:17:58,390 --> 00:18:01,330 scene one can actually be scheduled on the second day. 312 00:18:01,330 --> 00:18:04,402 You will never explore the fact that you know scene two can be scheduled on the 313 00:18:04,402 --> 00:18:08,020 third day, okay? So that's how you can break symmetries. 314 00:18:08,020 --> 00:18:10,900 Now this particular technique is very useful in practice. 315 00:18:10,900 --> 00:18:14,000 It has one limitation that I will talk about later in class, and that you can 316 00:18:14,000 --> 00:18:17,200 actually you know, you can actually remove that limitation by being a little 317 00:18:17,200 --> 00:18:21,980 bit clever. But I will come to that later on, okay? 318 00:18:21,980 --> 00:18:22,980 That's it.