1 00:00:00,260 --> 00:00:02,250 Okay, so last lecture on constraint programming. 2 00:00:02,250 --> 00:00:05,020 This is the square lecture. So, we're going to see a lot of problems 3 00:00:05,020 --> 00:00:07,545 on squares, magic squares, perfect squares. 4 00:00:07,545 --> 00:00:10,650 It's a really interesting thing. we are in search again. 5 00:00:10,650 --> 00:00:13,830 Okay, so trying to see various techniques for doing search. 6 00:00:13,830 --> 00:00:16,270 And once again you know, this is just introduction okay, so there are a lot 7 00:00:16,270 --> 00:00:19,040 more to this area, it's a very active research area. 8 00:00:19,040 --> 00:00:22,480 But I'm touching upon a number of topics that are interesting, okay. 9 00:00:22,480 --> 00:00:26,100 So we're going to try with value variable you know, labeling. 10 00:00:26,100 --> 00:00:29,581 Most people are going to do variable value labeling, and at some point you 11 00:00:29,581 --> 00:00:32,755 know, it's boring. So what we're going to do is something 12 00:00:32,755 --> 00:00:36,090 very different, which is called value/variable labeling. 13 00:00:36,090 --> 00:00:38,971 So instead of choosing the variable and then assigning the value, we want to look 14 00:00:38,971 --> 00:00:42,080 at the problem in a completely different fashion, right? 15 00:00:42,080 --> 00:00:45,356 We want to look at the value, and then choose a variable to which to assign the 16 00:00:45,356 --> 00:00:48,955 value, that value, okay? So take a value and then we take the 17 00:00:48,955 --> 00:00:52,240 variables to which we want to assign that value, okay? 18 00:00:52,240 --> 00:00:54,150 Now you're going to say, this is crazy, right? 19 00:00:54,150 --> 00:00:57,664 So this makes absolutely no sense, okay? But in practice they are a lot of 20 00:00:57,664 --> 00:01:00,304 applications where you know that a particular value has to be assigned, 21 00:01:00,304 --> 00:01:03,625 okay? This is typically happens in scheduling, 22 00:01:03,625 --> 00:01:07,272 this also happens. In time tabling problems where you know 23 00:01:07,272 --> 00:01:10,092 that a class has to assigned to something, a professor has to be assigned 24 00:01:10,092 --> 00:01:14,226 to particular classes and so on. Or in scheduling, you know that class has 25 00:01:14,226 --> 00:01:16,620 to start at a particular point in time, okay? 26 00:01:16,620 --> 00:01:19,430 So it's very useful in many applications, okay? 27 00:01:19,430 --> 00:01:22,460 So what I want to illustrate is that we've a really nice example. 28 00:01:22,460 --> 00:01:25,934 I'm going to get out of the way, okay? So what you see on the screen are 21 29 00:01:25,934 --> 00:01:29,760 different squares, okay? They are squares, and they all have a 30 00:01:29,760 --> 00:01:33,080 different size. Hello, okay, so I'm on the other side. 31 00:01:33,080 --> 00:01:37,250 Okay, and so the goal here is to look at all these squares, okay? 32 00:01:37,250 --> 00:01:41,060 And make them into one big square. Okay? 33 00:01:41,060 --> 00:01:44,954 So we have to pack them and arrange them in such a way that we make this big 34 00:01:44,954 --> 00:01:47,030 square. Okay? 35 00:01:47,030 --> 00:01:49,580 Now, I assume that you are completely bored at this point. 36 00:01:49,580 --> 00:01:52,225 You can't sleep. I'll let you look at this thing and you 37 00:01:52,225 --> 00:01:55,015 can spend the next 20 minutes trying to put all these squares inside the big 38 00:01:55,015 --> 00:01:58,614 square. It is very interesting, okay? 39 00:01:58,614 --> 00:02:02,878 So 20 minutes, okay? So and what I want, so this is one of the 40 00:02:02,878 --> 00:02:05,980 solutions, okay? You know won't let you look at it very 41 00:02:05,980 --> 00:02:08,878 quickly, you know, I won't let you look at it very long because I want you to be 42 00:02:08,878 --> 00:02:12,545 able to solve this puzzle so you can sleep right. 43 00:02:12,545 --> 00:02:15,730 So, so if we try to solve that using you know a constraint program, we have first 44 00:02:15,730 --> 00:02:19,480 to decide what the decision variables are going to be, okay? 45 00:02:19,480 --> 00:02:22,392 And they're going to be either x and y coordinates of every one of these 46 00:02:22,392 --> 00:02:25,860 squares. Okay the bottom left corner of one of 47 00:02:25,860 --> 00:02:28,946 every square. It could be the top right corner if you 48 00:02:28,946 --> 00:02:32,980 want, but you have to choose one and that's where you going to basically. 49 00:02:32,980 --> 00:02:34,930 That's what, the convention that you're going to use. 50 00:02:34,930 --> 00:02:37,267 In all particular case, we take the bottom left corner and that's the 51 00:02:37,267 --> 00:02:40,237 position of the square. As soon as you know these two, the x and 52 00:02:40,237 --> 00:02:43,508 y-coordinate of that corner, you know where the square is. 53 00:02:43,508 --> 00:02:45,340 Okay, what are there going to be the constraints? 54 00:02:45,340 --> 00:02:47,470 There are two type of constraints. This first one is easy. 55 00:02:47,470 --> 00:02:50,619 The squares have to fit in the, the small squares have to fit in the bigger square, 56 00:02:50,619 --> 00:02:53,550 and then obviously the square can't overlap. 57 00:02:53,550 --> 00:02:57,582 You want to make this big square, but you, you, you, you can't have the squares 58 00:02:57,582 --> 00:03:01,087 overlap, okay? Now, there are also some redundant 59 00:03:01,087 --> 00:03:03,212 constraints. Okay, so I won't go into all the details, 60 00:03:03,212 --> 00:03:07,380 but I want to give you the intuition. So here is the attrition, so if you look 61 00:03:07,380 --> 00:03:10,955 at that vertical line here, so that vertical line corresponds to X 62 00:03:10,955 --> 00:03:14,985 correlation and it's basically intersecting a number of squares, so what 63 00:03:14,985 --> 00:03:19,080 you want to be sure is essentially that the sum of the sizes of the square that 64 00:03:19,080 --> 00:03:23,370 this line is intersecting is equal to the size of the big square, ok so that is the 65 00:03:23,370 --> 00:03:27,660 redundant constraint that you have OK and this is essentially a model, its a you 66 00:03:27,660 --> 00:03:37,150 know a very wide model. OK expressing everything that I've told 67 00:03:37,150 --> 00:03:39,858 you about. OK so you have the decision variables 68 00:03:39,858 --> 00:03:42,978 which are the x and y coordinates there for everyone in the square then you have 69 00:03:42,978 --> 00:03:46,194 essentially a set of easy constraints there that are basically telling you that 70 00:03:46,194 --> 00:03:48,930 the square have to fit into large square and then you have two types of 71 00:03:48,930 --> 00:03:54,700 constraints that I mentioned. These are the redundant constraints. 72 00:03:54,700 --> 00:03:58,092 And they're basically, raise fine constraints for a particular position P, 73 00:03:58,092 --> 00:04:01,431 you're going to look at the square which are basically intersecting with that 74 00:04:01,431 --> 00:04:05,088 particular we've, we've I, actually intersecting with P okay, containing P in 75 00:04:05,088 --> 00:04:10,890 the sense and making sure that the size is the side of the big square. 76 00:04:10,890 --> 00:04:14,078 So this a [INAUDIBLE] constraints. And then you have the overlap constraint 77 00:04:14,078 --> 00:04:16,916 which are easy to save. Essentially if you have two square you 78 00:04:16,916 --> 00:04:20,255 have to make sure the square, one of the square is on the left, on the right, on 79 00:04:20,255 --> 00:04:25,229 top or on below the other square. Okay, so once again it's a big [UNKNOWN] 80 00:04:25,229 --> 00:04:27,920 of the various cases. Okay. 81 00:04:27,920 --> 00:04:31,060 So, but this is just a statement of the problem. 82 00:04:31,060 --> 00:04:34,160 What is interesting here is the value variable labeling. 83 00:04:34,160 --> 00:04:37,426 Why do we do that? Why, why don't we just place, you know, 84 00:04:37,426 --> 00:04:41,070 the various squares dis, different position? 85 00:04:41,070 --> 00:04:44,850 And the basic idea here is that we know that we have to fill this big square. 86 00:04:44,850 --> 00:04:47,160 And it's going to be completely filled, okay? 87 00:04:47,160 --> 00:04:51,560 So there is no empty space in that particular big square at the end. 88 00:04:51,560 --> 00:04:54,888 So we know that every time there is an empty space we have to place a particular 89 00:04:54,888 --> 00:04:58,220 square over there, okay? And that's why we are using a value 90 00:04:58,220 --> 00:05:00,940 labeling here. Okay, value variable labeling. 91 00:05:00,940 --> 00:05:04,120 Because, as soon as there is an empty space, you know, I know that I have to 92 00:05:04,120 --> 00:05:07,450 choose one particular square to be put there. 93 00:05:07,450 --> 00:05:09,707 And therefore I can just look at the square and choose which one is going to 94 00:05:09,707 --> 00:05:12,630 be placed there. Okay, visually, okay. 95 00:05:12,630 --> 00:05:15,142 So look at this, I placed one square, I placed another square. 96 00:05:15,142 --> 00:05:19,110 You know I know, I know for sure that one square will have to be placed there. 97 00:05:19,110 --> 00:05:23,132 Which one is it going to be? Okay, so another one and then a tiny one 98 00:05:23,132 --> 00:05:25,334 there. Oh, there is an empty space there which 99 00:05:25,334 --> 00:05:28,295 is the square that I'm going to have to place there, and that's the basic idea 100 00:05:28,295 --> 00:05:32,840 behind the value labeling procedure that I'm going to show you. 101 00:05:32,840 --> 00:05:36,380 Now you can write very complex one, or you can write a very simple one, I'm 102 00:05:36,380 --> 00:05:39,861 going to show you a very simple one which works almost as well as the most 103 00:05:39,861 --> 00:05:44,930 complicated well the most complicated ones. 104 00:05:44,930 --> 00:05:48,890 But it's actually very simple to state. So, so that's what I want to show you. 105 00:05:48,890 --> 00:05:50,590 Okay. So what we are going to do? 106 00:05:50,590 --> 00:05:53,374 Essentially what we are going to do is, what we are going to do is we're going to 107 00:05:53,374 --> 00:05:56,480 take this vertical slice. Let's say p, okay. 108 00:05:56,480 --> 00:06:00,325 And then we are going to decide, for all the square, do I place p there or not? 109 00:06:00,325 --> 00:06:03,080 Okay? So it's very, very simple, okay? 110 00:06:03,080 --> 00:06:07,190 I take all the x coordinate p. And on this side whether I place, you 111 00:06:07,190 --> 00:06:11,126 know, which squares do I place there? And then I move to the next coordinate, I 112 00:06:11,126 --> 00:06:13,780 do the same, and the same, and the same, and the same. 113 00:06:13,780 --> 00:06:16,270 And then I do the same for the y, and the y, and the y. 114 00:06:16,270 --> 00:06:19,770 And that's what I do, okay? So this is the search procedure, okay? 115 00:06:19,770 --> 00:06:22,660 Very simple I told you. We could do a more complicated one. 116 00:06:22,660 --> 00:06:25,370 But it doesn't bring very much, you know, benefit in practice. 117 00:06:25,370 --> 00:06:28,786 So I take, basically, all the X coordinates, okay, and then I need to 118 00:06:28,786 --> 00:06:32,568 read for all the squares that you see there, and then I decide, you know, do I 119 00:06:32,568 --> 00:06:37,840 place the particular square in that position, or not? 120 00:06:37,840 --> 00:06:39,860 Okay, and most of the time, it's going to be no's. 121 00:06:39,860 --> 00:06:41,770 But essentially that's all I have to do. Okay? 122 00:06:41,770 --> 00:06:45,750 So, these are for the x coordinate, and the bottom here is for the y coordinate. 123 00:06:45,750 --> 00:06:47,590 That's all I have to do in this particular case. 124 00:06:47,590 --> 00:06:50,420 Okay? So, it's a value variable labeling. 125 00:06:50,420 --> 00:06:53,885 I take a value and I decide you know, do I place it, is this square being placed 126 00:06:53,885 --> 00:06:59,494 at that particular location or not, okay? And this is very, very effective on this 127 00:06:59,494 --> 00:07:03,178 particular application, okay? So this is, basically what you're seeing 128 00:07:03,178 --> 00:07:05,560 now is variable/value labeling and value/variable labeling, okay? 129 00:07:05,560 --> 00:07:08,846 What I'm going to talk about now is a very complete, completely different way 130 00:07:08,846 --> 00:07:12,079 of actually branching which is called domain splitting and I'm going to use 131 00:07:12,079 --> 00:07:17,260 another square example which is called the magic square example, okay? 132 00:07:17,260 --> 00:07:19,490 So essentially, you have the number, okay? 133 00:07:19,490 --> 00:07:23,460 You have a num an, a set of numbers to be placed in a particular square. 134 00:07:23,460 --> 00:07:26,996 All the numbers have to be different, and then all the rows, columns and diagonals 135 00:07:26,996 --> 00:07:30,324 you know have to sum, you know with, when you look at the numbers, have to sum to 136 00:07:30,324 --> 00:07:36,030 the exact same number, okay? So this is a magic square of side three, 137 00:07:36,030 --> 00:07:39,348 okay? So you see the value 2, and 9, and 4, 138 00:07:39,348 --> 00:07:42,290 okay? So if you look at the sum of every one of 139 00:07:42,290 --> 00:07:46,420 these lines, okay? So this is one of these rows, okay? 140 00:07:46,420 --> 00:07:49,556 No, it's going to sum to, in this particular case, 15 so all these rules 141 00:07:49,556 --> 00:07:53,450 are going to sum to 15. You're going to look at all these columns 142 00:07:53,450 --> 00:07:57,110 now, they are also going to sum to 15 and the two diagnols are also going to solve 143 00:07:57,110 --> 00:08:00,770 to 15 so you see two, five and eight there that's basically fifteen and the 144 00:08:00,770 --> 00:08:05,968 other diagnaol is going to sum to 15. That's what you have to do. 145 00:08:05,968 --> 00:08:10,000 Okay, So basically, if you have, if you have a, if you have a square you know, 3 146 00:08:10,000 --> 00:08:13,626 by 3, okay? You know that you have to place a number 147 00:08:13,626 --> 00:08:16,859 between 1 and 9 in the square such that the sum of all the rows, the sum of all 148 00:08:16,859 --> 00:08:20,357 the columns, the sum of all the rows, and the sum of the two diagonals are equal to 149 00:08:20,357 --> 00:08:26,417 15 in this popular case. Okay, now this seem easy enough right so 150 00:08:26,417 --> 00:08:30,193 we could do that by hand okay what I wanted you to think about is can you do 151 00:08:30,193 --> 00:08:34,097 that for a square of 11 by 11 so we are going to place essentially 121 number in 152 00:08:34,097 --> 00:08:37,937 this particular square and we have to make sure that all the rows, all the 153 00:08:37,937 --> 00:08:41,713 rows, all the columns and all the two diagonals are going to sum to the same 154 00:08:41,713 --> 00:08:51,345 value, okay So how do you do that, okay. Now actually what you should really think 155 00:08:51,345 --> 00:08:55,249 is that can you actually serve that for a square which is a million by million, 156 00:08:55,249 --> 00:08:58,250 okay. And this can be done, okay. 157 00:08:58,250 --> 00:09:00,125 This can be actually can be done efficiently. 158 00:09:00,125 --> 00:09:04,444 Like you know for today, let us think of 11 by 11, okay? 159 00:09:04,444 --> 00:09:08,102 Now the key question here is that when you try to do that, which variable are 160 00:09:08,102 --> 00:09:12,180 you going to assign? So do you want really to assign? 161 00:09:12,180 --> 00:09:15,634 So, this is the solution to this one. So so, so one of the things that we need 162 00:09:15,634 --> 00:09:18,867 to think about is how you, how you are going to do the search for this 163 00:09:18,867 --> 00:09:23,890 particular example, okay? So before thinking about this, let's just 164 00:09:23,890 --> 00:09:27,460 think about what the statement of the problem here, okay? 165 00:09:27,460 --> 00:09:30,588 So what you see there basically the decision variable s, okay? 166 00:09:30,588 --> 00:09:34,809 That basically means for every square, you have to decide which values you give, 167 00:09:34,809 --> 00:09:38,022 okay? The values in this particular case are 168 00:09:38,022 --> 00:09:41,613 going to be between you know, if the square is of size 11 by 11, is going to 169 00:09:41,613 --> 00:09:46,967 be 11 square, so 121, okay? So, that's the domain of the variables, 170 00:09:46,967 --> 00:09:51,191 and then what you see here are the various constraints, okay? 171 00:09:51,191 --> 00:09:55,159 All the rows and the columns and the two diagonals and to sum to the same value T 172 00:09:55,159 --> 00:09:59,720 that can easily be pre-computed at the beginning, okay? 173 00:09:59,720 --> 00:10:03,070 And then you are forced to make sure that all the numbers, all the slots inside the 174 00:10:03,070 --> 00:10:06,020 square are different so you assign different values to every one of the 175 00:10:06,020 --> 00:10:09,010 slots. So, that's a statement of the problem, 176 00:10:09,010 --> 00:10:11,891 which is easy now. What is of course is the most interesting 177 00:10:11,891 --> 00:10:14,960 part is how do you actually, how do you actually do the search? 178 00:10:14,960 --> 00:10:17,688 Okay, so one of the things you could do is, you could, you know, select one of 179 00:10:17,688 --> 00:10:20,750 these squares. Okay, this one looks nice, okay? 180 00:10:20,750 --> 00:10:23,360 Well let's start there. And you could decide, oh I'm going to 181 00:10:23,360 --> 00:10:26,305 assign a value to that possible variable there. 182 00:10:26,305 --> 00:10:29,467 Okay, but essentially when you look at this thing, right, so this is the big 183 00:10:29,467 --> 00:10:34,780 square, right, you are going to take this variable and assign it a value, okay? 184 00:10:34,780 --> 00:10:38,040 But this is essentially completely random at this point, right? 185 00:10:38,040 --> 00:10:40,760 So you have absolutely no clue what you're doing, right? 186 00:10:40,760 --> 00:10:43,400 So, you're going to take a particular variable, take a value, but it's, you 187 00:10:43,400 --> 00:10:47,830 know, it's a completely random guess. And in addition to being very random 188 00:10:47,830 --> 00:10:51,060 guess, it's going to be a very strong commitment. 189 00:10:51,060 --> 00:10:53,958 You're basically saying, I want that particular variable to be that value, 190 00:10:53,958 --> 00:10:57,170 okay? So can we do something which is like a 191 00:10:57,170 --> 00:11:00,470 weaker commitment, okay. And that's what we're going to do. 192 00:11:00,470 --> 00:11:03,308 So, domain splitting is basically you're going to select a variable, and instead 193 00:11:03,308 --> 00:11:07,100 of assigning a particular value, you're going to say ooh, wait a minute, right? 194 00:11:07,100 --> 00:11:09,930 So, I don't want to make a big decision here, right? 195 00:11:09,930 --> 00:11:13,179 So, what I'm going to say is that I'm going to you know, see if I can actually 196 00:11:13,179 --> 00:11:16,656 find a solution if I assign you know, a value which is in the upper half of my 197 00:11:16,656 --> 00:11:22,572 domain or the bottom half of my domain. Okay, so you split the domain in two, and 198 00:11:22,572 --> 00:11:25,512 you say, okay, so I'm going to try to place this particular value, that this 199 00:11:25,512 --> 00:11:28,746 particle, I'm going to basically assume that that variable is in the upper domain 200 00:11:28,746 --> 00:11:33,060 or the lower domain of, of, of its actual domain. 201 00:11:33,060 --> 00:11:36,400 Okay, and this is what we can do. And this is a search procedure expressing 202 00:11:36,400 --> 00:11:38,776 you that. Once again you are going to, you are 203 00:11:38,776 --> 00:11:41,610 going to loop until you assign all the variables, okay? 204 00:11:41,610 --> 00:11:44,949 At every one you select a variable using the first [UNKNOWN] principle, so a 205 00:11:44,949 --> 00:11:48,712 variable which is very tough to actually assign, and what this is doing here, here 206 00:11:48,712 --> 00:11:53,410 is not assigning a popular value to that variable. 207 00:11:53,410 --> 00:11:55,450 What you do is you take the midpoint in the domain. 208 00:11:55,450 --> 00:11:57,410 That's the mid value that you see there, okay? 209 00:11:57,410 --> 00:12:00,033 And then you basically say, oh, the variable has to be smaller than the mid 210 00:12:00,033 --> 00:12:04,706 value, or greater than the mid value. So the choice that you do here, okay, is 211 00:12:04,706 --> 00:12:07,610 much weaker. You are basically assuming that the 212 00:12:07,610 --> 00:12:11,350 variable is inside a subtle value. But you haven't specified which one. 213 00:12:11,350 --> 00:12:14,990 So it's a much weaker commitment, and since we have absolutely no clue in this, 214 00:12:14,990 --> 00:12:18,182 no clue in this particular problem, what to do, this is going to be a very 215 00:12:18,182 --> 00:12:23,290 effective strategy in this particular example, okay? 216 00:12:23,290 --> 00:12:26,030 So you're going to say oh yeah, but this is a puzzle. 217 00:12:26,030 --> 00:12:30,566 Now this strategy, is actually extremely good For very hard car sequencing 218 00:12:30,566 --> 00:12:33,327 problems. So remember we showed that before a 219 00:12:33,327 --> 00:12:37,280 couple of lectures ago. So you cars on an assembly line. 220 00:12:37,280 --> 00:12:40,764 Every one of these beautiful cars okay, is basically requiring some options you 221 00:12:40,764 --> 00:12:44,040 know, a moon roof or leather seats and things like this Now to actually prune 222 00:12:44,040 --> 00:12:47,472 these options on the cars you have these production units, which are basically 223 00:12:47,472 --> 00:12:50,748 putting these thing as the car is moving in front of the production unit, and 224 00:12:50,748 --> 00:12:57,477 therefor you have to be careful. You have to sequence the, the car in such 225 00:12:57,477 --> 00:13:01,430 a way that you have the time to actually put the various options on every one as 226 00:13:01,430 --> 00:13:06,340 the car is moving in front of the production unit, okay? 227 00:13:06,340 --> 00:13:09,210 So we add the first time I've shown you that. 228 00:13:09,210 --> 00:13:12,226 Essentially a simple, variable value strategy, okay? 229 00:13:12,226 --> 00:13:15,905 Which for a lot of instances is actually working pretty nicely. 230 00:13:15,905 --> 00:13:19,382 But on some of the very hard instances, and some of the instances which are 231 00:13:19,382 --> 00:13:24,660 actually invisible, it's not the best strategy that you could use. 232 00:13:24,660 --> 00:13:28,125 And one of the things that you have to recognize here is that the options that 233 00:13:28,125 --> 00:13:31,874 you see here, okay? They have different strengths, some of 234 00:13:31,874 --> 00:13:35,084 them are really tight. Okay, so lets say the first two here are 235 00:13:35,084 --> 00:13:37,840 really tight. There is essentially no slack. 236 00:13:37,840 --> 00:13:41,770 It is very difficult to insert a new car. With that popular option. 237 00:13:41,770 --> 00:13:46,130 And when you look at the some of the, the other options that you see there, okay? 238 00:13:46,130 --> 00:13:49,416 Especially, the fourth option, for instance, it's a very, you know, loose 239 00:13:49,416 --> 00:13:52,755 option in a sense, there are many ways you could actually place all the cars, 240 00:13:52,755 --> 00:13:58,245 there are plenty of areas where you see essentially no cars being placed. 241 00:13:58,245 --> 00:14:01,625 Okay, so in a sense when you are trying to solve these problems you know what you 242 00:14:01,625 --> 00:14:04,745 want to do, and this is once again the first real principle, is focus on the 243 00:14:04,745 --> 00:14:08,950 options that are really really difficult, okay. 244 00:14:08,950 --> 00:14:12,870 But once again, you don't really care about the various types of cars. 245 00:14:12,870 --> 00:14:16,713 What you really care about is you know, do I you know, do I place a car in this 246 00:14:16,713 --> 00:14:21,400 particular slot, requiring that options or not, okay? 247 00:14:21,400 --> 00:14:24,650 So, what you want is not reasoning about the different types of car, you want to 248 00:14:24,650 --> 00:14:28,914 reason about the various options, okay? And you want to focus first on the 249 00:14:28,914 --> 00:14:33,368 options that are very difficult. And then you decide you know if you place 250 00:14:33,368 --> 00:14:37,630 a car requesting that option, okay? In that particular site but you are not 251 00:14:37,630 --> 00:14:41,095 actually placing car you are saying aw there will be a car in that particular 252 00:14:41,095 --> 00:14:45,790 option but I don't want to commit to which car at this point. 253 00:14:45,790 --> 00:14:49,066 Okay, and this is the key idea that you are focusing on all the options and for 254 00:14:49,066 --> 00:14:54,223 the option that are really difficult. And so in a sense, the way to do this is, 255 00:14:54,223 --> 00:14:58,065 is, is very natural. Okay, so what you do, is that you do a 256 00:14:58,065 --> 00:15:01,960 search procedure which iterates over the options. 257 00:15:01,960 --> 00:15:04,640 We are not iterating over the various types of count. 258 00:15:04,640 --> 00:15:08,475 We are looking at the various options, and then for every line of the assembly, 259 00:15:08,475 --> 00:15:12,310 every slot of the assembly line, we are deciding if that particular slot in the 260 00:15:12,310 --> 00:15:16,676 assembly line is taking the option, does the first That's the first that's, that's 261 00:15:16,676 --> 00:15:23,800 the first choice that you can make there or it's not taking the option. 262 00:15:23,800 --> 00:15:27,035 Okay, so why does it work? Because you look at every one of the 263 00:15:27,035 --> 00:15:30,005 options, and if that for every one of the slot in the assembly line, you're going 264 00:15:30,005 --> 00:15:33,332 to decide do I think that option is enough, okay? 265 00:15:33,332 --> 00:15:37,280 Not assigning the car, but then you take the next option, you do the same thing. 266 00:15:37,280 --> 00:15:40,100 And so at the end of the day what we are going to do, is for every one of these 267 00:15:40,100 --> 00:15:42,826 things, you are going to choose very specific configuration because 268 00:15:42,826 --> 00:15:45,834 essentially the other constraints are forcing you to choose between which, 269 00:15:45,834 --> 00:15:51,235 which they are basically forcing the type of car you have to produce. 270 00:15:51,235 --> 00:15:54,842 Okay, so very interesting here. What you do is essentially domain 271 00:15:54,842 --> 00:15:57,663 splitting. Every time you make a choice here, you 272 00:15:57,663 --> 00:16:01,884 are basically splitting for the particle of slot variable, the set of cars in two 273 00:16:01,884 --> 00:16:06,085 parts. The one that they are requiring the 274 00:16:06,085 --> 00:16:10,000 options, or the one not requiring the options, okay? 275 00:16:10,000 --> 00:16:12,961 So then you choose first to assigne cars for the options, and then the car not 276 00:16:12,961 --> 00:16:16,354 taking the options. Okay, so essentially, this is once again 277 00:16:16,354 --> 00:16:19,400 a domain splitting. You have a mutual commitment. 278 00:16:19,400 --> 00:16:22,046 The only thing you are doing is deciding whether you add that option for that 279 00:16:22,046 --> 00:16:25,841 particular slot or not. Okay, very effective on some of the most 280 00:16:25,841 --> 00:16:29,747 difficult car sequencing instances, especially when you want to prove 281 00:16:29,747 --> 00:16:33,686 infeasibility, okay? So, so far we have seen a lot of 282 00:16:33,686 --> 00:16:37,162 different things, okay? Variable/value symmetry. 283 00:16:37,162 --> 00:16:40,820 Value/variable symmetry, okay? We have seen that we can use a first 284 00:16:40,820 --> 00:16:43,745 weighted principle by using physical linking formation, and sometime using 285 00:16:43,745 --> 00:16:47,914 the, the objective function. And we have seen that in some instances, 286 00:16:47,914 --> 00:16:51,684 okay, we, we wanted a weaker commitment and new domain splitting What I want to 287 00:16:51,684 --> 00:16:55,338 do now is come back to, you know I promised you that, come back to symmetry 288 00:16:55,338 --> 00:16:59,108 breaking and look at how we can actually break symmetry breaking, not by using 289 00:16:59,108 --> 00:17:07,170 constraints, but during the search, okay? You will see why this is important, okay? 290 00:17:07,170 --> 00:17:10,550 And we going to go back to this scene allocation problem, right? 291 00:17:10,550 --> 00:17:16,670 So these beautiful people, you know, Georges, and Julia, and Clyde. 292 00:17:16,670 --> 00:17:21,320 You know, I like Clive a lot, so you do it, it was almost James Bond. 293 00:17:21,320 --> 00:17:24,570 Or maybe that was just a marketing, you know, ploy that he had. 294 00:17:24,570 --> 00:17:27,180 But he would have been really great James Bond. 295 00:17:27,180 --> 00:17:29,500 Anyway, Dan Craig is a great James Bond too. 296 00:17:29,500 --> 00:17:31,970 But anyway, so I'm getting ahead of myself here. 297 00:17:31,970 --> 00:17:35,750 So what we are trying to do is shoot these beautiful movies, okay. 298 00:17:35,750 --> 00:17:38,606 And the actor plays in different scenes, and remember, they were paid by the scene 299 00:17:38,606 --> 00:17:42,770 that they They play with. And they were not, you know, paid by the 300 00:17:42,770 --> 00:17:46,466 scene they played with, they were paid by the number of days that they were on the 301 00:17:46,466 --> 00:17:49,880 set, okay? And we had constraints on the number of 302 00:17:49,880 --> 00:17:52,310 scenes that you can...that you can shoot every day. 303 00:17:52,310 --> 00:17:55,901 So you can shoot at most k scenes every day And the objective was obviously to 304 00:17:55,901 --> 00:17:59,549 minimize the cost, and one way to do that is make sure that the actors when they 305 00:17:59,549 --> 00:18:05,700 spend a day on the cast are basically shooting as many scenes as possible. 306 00:18:05,700 --> 00:18:08,780 Note there were a lot of symmetries on this particular product. 307 00:18:08,780 --> 00:18:11,920 Do you remember? Okay, so the symmetries were about the 308 00:18:11,920 --> 00:18:14,906 various days, right? So, The days, at the beginning, were all 309 00:18:14,906 --> 00:18:18,442 interchangeable, Monday and Tuesday, they were no difference for these actors, 310 00:18:18,442 --> 00:18:21,490 okay? So the way we eliminated those symmetries 311 00:18:21,490 --> 00:18:24,952 by putting constraints, okay? So the first scene that we wanted to 312 00:18:24,952 --> 00:18:27,800 assign, okay? The things that we said was that, you 313 00:18:27,800 --> 00:18:30,510 know, it was day one. It could be only assigned to day one, 314 00:18:30,510 --> 00:18:33,600 because at that point, all the days were the same. 315 00:18:33,600 --> 00:18:36,610 For the second scene we were considering, we were basically saying okay, that scene 316 00:18:36,610 --> 00:18:40,270 can be assigned to day one, that's where scene one has been allocated. 317 00:18:40,270 --> 00:18:43,000 Or a new day, which is basically day two because all the other days are the same, 318 00:18:43,000 --> 00:18:48,150 at this point, are essentially [UNKNOWN]. And so in a general fashion, when you 319 00:18:48,150 --> 00:18:51,200 look at saying I, you were basically looking at the day that were assigned 320 00:18:51,200 --> 00:18:54,813 before, plus a new day. And that's what this beautiful formula 321 00:18:54,813 --> 00:18:57,741 was telling you. And so what we did was, you know, doing 322 00:18:57,741 --> 00:19:01,158 this nice model, and then you have the symmetry breaking constraints where, you 323 00:19:01,158 --> 00:19:04,269 are basically saying that scene 1 is allocated to 1, and then all the other 324 00:19:04,269 --> 00:19:07,584 scenes were allocating to the values assigned to the previous scene plus a new 325 00:19:07,584 --> 00:19:12,630 one. Okay, and so you were basically, what we 326 00:19:12,630 --> 00:19:18,390 were doing, what basically putting all these constraints Inside the model, okay? 327 00:19:18,390 --> 00:19:20,250 So there are symmetry breaking constraints. 328 00:19:20,250 --> 00:19:22,850 They were getting rid of the symmetries in the popular instant, in the popular 329 00:19:22,850 --> 00:19:26,391 problem. And, and, and, and, and these symmetries 330 00:19:26,391 --> 00:19:30,740 were basically taken care of by putting these additional constraints, okay? 331 00:19:30,740 --> 00:19:34,140 Now, when you think about this and you think about search. 332 00:19:34,140 --> 00:19:38,190 These constraints have the dramatic effect on search, right? 333 00:19:38,190 --> 00:19:42,080 So if you use the first [INAUDIBLE] principle, what's going to happen, okay? 334 00:19:42,080 --> 00:19:45,676 Essentially, these constraints are going to dictate the, mostly the way you 335 00:19:45,676 --> 00:19:49,409 are basically doing search, why? Because the first scene is already 336 00:19:49,409 --> 00:19:53,033 allocating, there is no choice. Then you look at the second scene, which 337 00:19:53,033 --> 00:19:56,680 is in the positive order in which we stated the problem, right? 338 00:19:56,680 --> 00:20:00,712 So, that 2nd scene is the domain of 2. The 3rd scene, as the most domain of 3. 339 00:20:00,712 --> 00:20:04,677 The, the 4th scene most a domain of 4. So essentially, from a, when you use the 340 00:20:04,677 --> 00:20:07,764 first stated principal, you are basically, by stating these constraints, 341 00:20:07,764 --> 00:20:12,508 you are basically choosing the order in which you have to assign the variable. 342 00:20:12,508 --> 00:20:15,540 Is that good? Well sometimes yes, sometimes no. 343 00:20:15,540 --> 00:20:18,454 But in this particularly case, it essentially prevents you from using any 344 00:20:18,454 --> 00:20:21,603 kind of sophisticated characteristic because it's basically you know, you're 345 00:20:21,603 --> 00:20:24,987 basically constrained by this, this, this constraint that I'm basically reusing the 346 00:20:24,987 --> 00:20:29,620 domain of the variable. So can we avoid it? 347 00:20:29,620 --> 00:20:32,854 So there is an interferance between the symmetry breaking constraints and the 348 00:20:32,854 --> 00:20:36,736 search heuristic that you could use. If you wanted for instance to use a 349 00:20:36,736 --> 00:20:40,012 heuristic that was using the first principal, the smallest domain and they 350 00:20:40,012 --> 00:20:44,670 save the [UNKNOWN] most expensive ones first, you are not doing that. 351 00:20:44,670 --> 00:20:47,820 Because essentially these symmetry you know these symmetry breaking constraints 352 00:20:47,820 --> 00:20:51,860 were imposing a particular order. So can we actually get rid of this and 353 00:20:51,860 --> 00:20:55,146 the, the answer is yes. And what we have to do is take the 354 00:20:55,146 --> 00:20:58,674 symmetry breaking constraints and not impose them in the modern but kind of 355 00:20:58,674 --> 00:21:02,520 introduce them dynamically during the search. 356 00:21:02,520 --> 00:21:06,670 So we're going to impose essentially the same, same symmetry breaking constraints. 357 00:21:06,670 --> 00:21:10,104 But dynamically during the search. Okay, so in a sense what we the big 358 00:21:10,104 --> 00:21:13,866 difference between imposing them inside the model and imposing them doing the 359 00:21:13,866 --> 00:21:17,172 search is that the ordering is going to be different and its going to be 360 00:21:17,172 --> 00:21:20,649 discovered incrementally by looking at the variables which are the most 361 00:21:20,649 --> 00:21:27,824 difficult to assign. Okay, so, so in a sense what we're 362 00:21:27,824 --> 00:21:31,382 going to do. The, the search heuristic is going to be 363 00:21:31,382 --> 00:21:34,658 the search heuristic is going to be, you know, choosing the next scene and that 364 00:21:34,658 --> 00:21:38,090 next scene will take the one which is the smallest domain between [UNKNOWN] the 365 00:21:38,090 --> 00:21:44,350 first fail principle and in case of time we'll take the most expensive scene. 366 00:21:44,350 --> 00:21:47,867 What, why would, would we do that? Because those [UNKNOWN] if, if they are 367 00:21:47,867 --> 00:21:51,407 many of these actors that are very expensive, we want to start with these 368 00:21:51,407 --> 00:21:55,242 scenes because essentially, you know, that will give us a, that will increase 369 00:21:55,242 --> 00:22:00,540 the directly the value of the objective function. 370 00:22:00,540 --> 00:22:03,346 If we place that particular thing and some of the actors, you know this is a 371 00:22:03,346 --> 00:22:06,630 new day for them or no, this is not a new day for them. 372 00:22:06,630 --> 00:22:09,450 That will have a dramatic effect on the objective function. 373 00:22:09,450 --> 00:22:12,348 So the heuristic is going to take the scenes which have the smallest domain and 374 00:22:12,348 --> 00:22:14,970 in case of ties we're going to break that by looking at the scene which is 375 00:22:14,970 --> 00:22:17,960 expansive, which basically means, you know, the scene which contains a lot of 376 00:22:17,960 --> 00:22:23,104 actors whose fees are very high, okay? So, now essentially we have to choose 377 00:22:23,104 --> 00:22:27,170 what we are going to do, so we have to break the symmetries during the search. 378 00:22:27,170 --> 00:22:30,456 So when we take it, when we take a scene like this, we're left to decide which 379 00:22:30,456 --> 00:22:34,330 days we will consider for that particular scene. 380 00:22:34,330 --> 00:22:36,940 And, once again, we're going to do exactly the same trick as we did for the 381 00:22:36,940 --> 00:22:39,997 static constraint. We're going to take the existing days 382 00:22:39,997 --> 00:22:42,924 plus one, a new one, okay? But now, we are not imposing these 383 00:22:42,924 --> 00:22:46,510 constraints inside the model, right? So we are imposing them during the 384 00:22:46,510 --> 00:22:49,348 search, okay? So when we label the scene with the only 385 00:22:49,348 --> 00:22:52,239 values we will consider for that particular scene, so the values of the 386 00:22:52,239 --> 00:22:55,640 days that we have used before, plus one, okay? 387 00:22:55,640 --> 00:22:59,290 And the advantages here is that you essentially break the same symmetries. 388 00:22:59,290 --> 00:23:02,533 You break the same symmetries, you break, you sometimes, you use the constraints a 389 00:23:02,533 --> 00:23:05,353 little bit later, but they don't interfere with the search heuristic at 390 00:23:05,353 --> 00:23:09,480 this point. They don't change your euristic by simply 391 00:23:09,480 --> 00:23:13,288 by putting by putting these constraint dynamically during the search, you don't 392 00:23:13,288 --> 00:23:17,760 change the euristic. Okay, so this is what you can do here. 393 00:23:17,760 --> 00:23:20,440 This is essentially the search procedure expressing that. 394 00:23:20,440 --> 00:23:24,125 So what you see here is that when you try the value for the particular variable you 395 00:23:24,125 --> 00:23:27,790 take the exitsing data to compute it above there. 396 00:23:27,790 --> 00:23:30,230 Okay, that's the days you have already used. 397 00:23:30,230 --> 00:23:33,342 And then you take a new one, okay? So, that's how you're going to break the 398 00:23:33,342 --> 00:23:35,745 symmetries there. You don't consider all the possible value 399 00:23:35,745 --> 00:23:38,890 in the domain of the variables. The only thing that you do is you take 400 00:23:38,890 --> 00:23:42,706 the existing days plus a new one. That's the only value that you select for 401 00:23:42,706 --> 00:23:46,947 that [INAUDIBLE]. Of course, what you see on top of there 402 00:23:46,947 --> 00:23:51,760 is basically selecting the, the minimum value. 403 00:23:51,760 --> 00:23:55,840 the minimum value, the, what you do there is select sine, which is the smallest 404 00:23:55,840 --> 00:24:00,620 domain, and then in case of [UNKNOWN] the most expansive, okay? 405 00:24:00,620 --> 00:24:04,104 So, that, you see a basically a dynamic coloring there, choosing the one which is 406 00:24:04,104 --> 00:24:08,970 the smallest domain and this is not actually influenced or impacted. 407 00:24:08,970 --> 00:24:12,746 By the Symmetry Breaking constraint and then the one and in case of tie the one 408 00:24:12,746 --> 00:24:16,545 that is the most expensive. Okay, so once again this is the 409 00:24:16,545 --> 00:24:19,632 essentially the same Symmetry Breaking ID, the difference is that we don't 410 00:24:19,632 --> 00:24:22,964 impose any static in the model what we do is we actually introduce this constraint 411 00:24:22,964 --> 00:24:26,247 dynamically during the search by limiting the set of values that we consider for 412 00:24:26,247 --> 00:24:31,661 everyone of the variables. Okay, so this is the, the, the last 413 00:24:31,661 --> 00:24:35,257 technique though that I want to talk about, which is randomization and 414 00:24:35,257 --> 00:24:38,508 restarts. Okay, so we'll come back to this when we 415 00:24:38,508 --> 00:24:41,280 talk about large number root search, which is the most sophisticated use of 416 00:24:41,280 --> 00:24:44,418 this. But what I'm going to talk about now is 417 00:24:44,418 --> 00:24:48,188 very simple, but it can be very powerful for some example, okay? 418 00:24:48,188 --> 00:24:51,672 And so, the basic key intuition here is that sometimes there is no obvious search 419 00:24:51,672 --> 00:24:56,480 ordering, but the structure of the problem is such that there is one. 420 00:24:56,480 --> 00:25:00,676 We just don't know which one it is, okay? Alright, so this kind of interesting 421 00:25:00,676 --> 00:25:05,310 problems where there is a good ordering but it's very difficult to find it. 422 00:25:05,310 --> 00:25:08,470 So, what do you do when you are in a situation like that? 423 00:25:08,470 --> 00:25:12,105 You know that there is a good ordering, but you don't know which one. 424 00:25:12,105 --> 00:25:14,618 We, you don't know where it is. So what we going to have to use is brute 425 00:25:14,618 --> 00:25:17,110 force, right? Completely stupid. 426 00:25:17,110 --> 00:25:20,060 What we are going to do, is we going to randomize, okay? 427 00:25:20,060 --> 00:25:23,080 We going to randomly generate it some ordering. 428 00:25:23,080 --> 00:25:25,620 Hopefully we'll, we'll try to find it good ones. 429 00:25:25,620 --> 00:25:28,534 And then if this doesn't work, if we can't find the solution in a reasonable 430 00:25:28,534 --> 00:25:31,495 time, we're just going to restart, generate another ordering, and try, and 431 00:25:31,495 --> 00:25:36,160 try, and try to see if we can find solution with that ordering, okay? 432 00:25:36,160 --> 00:25:38,756 So, the key idea is that we try, you know, we try something, if it doesn't 433 00:25:38,756 --> 00:25:42,410 work, we stop early, right? So we say ooh this is looking really bad 434 00:25:42,410 --> 00:25:45,710 and you try another ordering and we try to see if we can do better with that 435 00:25:45,710 --> 00:25:51,468 ordering, okay? So in a sense the key idea is to try a 436 00:25:51,468 --> 00:25:55,332 variety of random ordering. We execute the search with those 437 00:25:55,332 --> 00:25:57,412 ordering. If it doesn't work after a, after a 438 00:25:57,412 --> 00:26:01,280 certain time limit or a number limits on the number of failures. 439 00:26:01,280 --> 00:26:04,646 You restart the search and you see if we have another ordering you can do better, 440 00:26:04,646 --> 00:26:07,463 okay? So this is very useful for this magic 441 00:26:07,463 --> 00:26:10,607 square problem for instance. So when you so, look at this thing, I 442 00:26:10,607 --> 00:26:13,402 told you before, we can assign a value to a variable we also in no clue what we are 443 00:26:13,402 --> 00:26:16,560 doing. Even when we do domain splitting, we 444 00:26:16,560 --> 00:26:20,726 basically have no clue what we are doing. But on this particular problem, sometimes 445 00:26:20,726 --> 00:26:23,950 you have good orderings that aren't going to make a big difference, okay? 446 00:26:23,950 --> 00:26:26,410 So where do we start? We don't know, so what we're going to do 447 00:26:26,410 --> 00:26:30,630 is we basically going to randomize okay? So instead of choosing essentially the 448 00:26:30,630 --> 00:26:33,830 variable which has the smallest domain, okay, we're going to select let's say, 449 00:26:33,830 --> 00:26:36,880 one of the tree of best variables, one of the tree variable we should have a 450 00:26:36,880 --> 00:26:40,937 smallest domain. We just randomize the search a little 451 00:26:40,937 --> 00:26:44,640 bit, we don't commit to the variable which has the smallest domain. 452 00:26:44,640 --> 00:26:47,840 And then we're going to limit the amount of time we spend, and if we exhaust the 453 00:26:47,840 --> 00:26:50,890 time limit we're just going to basically restart the search, possibly by 454 00:26:50,890 --> 00:26:54,040 increasing the time limit so that we Improve the, you know, the chance of you 455 00:26:54,040 --> 00:26:59,342 actually finding a solution. And this is the only thing that you have 456 00:26:59,342 --> 00:27:02,041 to do, okay? To do that, so what you see you know, in 457 00:27:02,041 --> 00:27:05,458 shadow gray over there, are basically you know, the search procedures that I've 458 00:27:05,458 --> 00:27:10,000 shown you before. And we are making very, very few changes. 459 00:27:10,000 --> 00:27:12,900 One of the changes that you see there is that you are randomizing. 460 00:27:12,900 --> 00:27:16,368 Instead of selecting the variable with the smallest domain, we are selecting one 461 00:27:16,368 --> 00:27:20,360 of the three variables, which have the smallest domain you know? 462 00:27:20,360 --> 00:27:23,879 And then essentially we have these repeat loop which is basically restarting this 463 00:27:23,879 --> 00:27:26,488 search. Okay, and we are making sure that we can 464 00:27:26,488 --> 00:27:30,825 only search for a certain time limit. Okay, and if we fail, you know, finding a 465 00:27:30,825 --> 00:27:34,610 solution, when we restart, we increase the time limit. 466 00:27:34,610 --> 00:27:37,240 That's all we have to do for actually implementing this, okay? 467 00:27:37,240 --> 00:27:40,300 So what we do, basically we do the search here, you know, it's randomized, so we're 468 00:27:40,300 --> 00:27:43,780 going to pick up the variable ordering in a random fashion. 469 00:27:43,780 --> 00:27:47,370 If you find the solution great. Okay, if we don't after a certain time we 470 00:27:47,370 --> 00:27:50,280 restart. We increase the time limit. 471 00:27:50,280 --> 00:27:54,311 We re execute this procedure. Which basically means that we're going to 472 00:27:54,311 --> 00:27:58,372 find another random ordering for this particular variable, okay? 473 00:27:58,372 --> 00:28:01,963 And, and we're going to search with that particular random ordering and if you 474 00:28:01,963 --> 00:28:05,534 find that solution great. Otherwise we'll redo this thing until we 475 00:28:05,534 --> 00:28:09,395 find the partiuclar solution. Okay, so this is kind of brute force, 476 00:28:09,395 --> 00:28:11,560 okay? Once again, it's combining all the 477 00:28:11,560 --> 00:28:14,390 techniques that we've seen before. We can put anything in there. 478 00:28:14,390 --> 00:28:17,198 But on top of this, we are basically introducing this restart and 479 00:28:17,198 --> 00:28:21,785 randomization, which can be very powerful for some classes of application. 480 00:28:21,785 --> 00:28:26,009 Okay, so at this point we have basically covered all the lectures on constraint 481 00:28:26,009 --> 00:28:29,610 programming. The next set of lectures are going to 482 00:28:29,610 --> 00:28:33,496 look at local search and look at very, some of the same problems using a 483 00:28:33,496 --> 00:28:37,490 different technology. Thank you very much. 484 00:28:37,490 --> 00:28:37,490 [BLANK_AUDIO].