1 00:00:00,240 --> 00:00:04,359 discrete optimization, before last lecture on constraint programming, okay? 2 00:00:04,359 --> 00:00:07,479 So, one of the things that I told you in the beginning is that there are two 3 00:00:07,479 --> 00:00:11,970 aspects which are really critical in a constraint programming system. 4 00:00:11,970 --> 00:00:15,234 One of them is constraint propagation, and we spend a lot of looking at that in 5 00:00:15,234 --> 00:00:19,158 the, in the past lectures. And what I'm going to, the other, the 6 00:00:19,158 --> 00:00:21,356 other one is search. And that's what we're going to talk about 7 00:00:21,356 --> 00:00:26,050 in the next two lectures. It's also a very active area of research. 8 00:00:26,050 --> 00:00:28,795 And if for what I'm going to talk about today is basically an introduction to 9 00:00:28,795 --> 00:00:32,004 some of the concepts. Basic introduction once again, to make 10 00:00:32,004 --> 00:00:34,585 you curious, right? So, the key idea in constraint 11 00:00:34,585 --> 00:00:38,566 programming is that search is based on feasibility information, okay? 12 00:00:38,566 --> 00:00:42,223 So what the constraint programming system is doing very well is basically pruning 13 00:00:42,223 --> 00:00:45,933 the search base, based on constraints and feasibility, making sure that, you know, 14 00:00:45,933 --> 00:00:49,550 as many of these constraints are feasible. 15 00:00:49,550 --> 00:00:51,955 And the search, of course, is going to explore that information, because that's 16 00:00:51,955 --> 00:00:55,035 the big information that we have in a constraint programming system. 17 00:00:55,035 --> 00:00:57,278 Okay? So what does it mean to explore this, 18 00:00:57,278 --> 00:01:01,217 this feasibility information? So we, we have this, very high level 19 00:01:01,217 --> 00:01:06,140 principle that we want to apply, which is called the first-fail principle. 20 00:01:06,140 --> 00:01:08,940 And it's very counterintuitive. But actually, it makes a lot of sense. 21 00:01:08,940 --> 00:01:12,620 So, so what you are trying to do. So, the, the, the principle tells you. 22 00:01:12,620 --> 00:01:15,750 Try first where you are the most likely to fail, okay? 23 00:01:15,750 --> 00:01:17,885 So, and the way to think about this is that you have a bunch of tasks that you 24 00:01:17,885 --> 00:01:20,490 have to accomplish. And you get a reward if you accomplish 25 00:01:20,490 --> 00:01:23,410 them all. And one of them is really hard. 26 00:01:23,410 --> 00:01:26,264 Don't postpone it, focus on it. Because the easy stuff, you know, you can 27 00:01:26,264 --> 00:01:29,880 do the easy stuff but you are wasting your time if you can't do the hard stuff. 28 00:01:29,880 --> 00:01:32,010 That's what this principle is telling you. 29 00:01:32,010 --> 00:01:35,018 Try first, you know, where it's the most, when you are the most likely to fail, 30 00:01:35,018 --> 00:01:39,460 because you want to fail early, okay? And so, essentially what it means is 31 00:01:39,460 --> 00:01:42,694 that, you don't want to spend time doing the early stuff, and then go to the tough 32 00:01:42,694 --> 00:01:45,585 stuff and see that, no I can't do the tough stuff, go back and try to do the 33 00:01:45,585 --> 00:01:48,672 easy stuff in another way, such that, in the hope that the hard stuff is going to 34 00:01:48,672 --> 00:01:54,510 be a little bit easier. That's not what we want to do, okay? 35 00:01:54,510 --> 00:01:57,730 We want to start with the hard stuff as quickly as possible. 36 00:01:57,730 --> 00:02:00,439 And of course by starting with the hard stuff what we hope is that we'll have a 37 00:02:00,439 --> 00:02:04,182 very small search tree. And that easy stuff we can take care of 38 00:02:04,182 --> 00:02:06,960 at the end. So, that's the first-fail principle. 39 00:02:06,960 --> 00:02:10,275 You want to start first with where you are the most likely to fail. 40 00:02:10,275 --> 00:02:12,160 Okay? Now, what does it mean? 41 00:02:12,160 --> 00:02:15,090 Well, look at this beautiful queens example that we have. 42 00:02:15,090 --> 00:02:16,882 Okay? So, what does it mean to, to look at 43 00:02:16,882 --> 00:02:20,745 something which is though, where you are most likely to fail? 44 00:02:20,745 --> 00:02:24,458 Okay, now all these queens, they have different set of values, okay? 45 00:02:24,458 --> 00:02:28,880 And what you want to do is to start with one, which is as few values as possible. 46 00:02:28,880 --> 00:02:31,636 This one is only one value. You know that you have to place the 47 00:02:31,636 --> 00:02:34,539 queens there, okay? Now, if there are some values which have, 48 00:02:34,539 --> 00:02:37,453 some queens have four values, and some which have two, you want to start with 49 00:02:37,453 --> 00:02:42,150 the ones which have only two values. They're harder to place and that's where 50 00:02:42,150 --> 00:02:45,875 you want to start from. Now we're also constructing smaller 51 00:02:45,875 --> 00:02:49,065 searchbase because you only have a branching, you know, factor of two 52 00:02:49,065 --> 00:02:53,105 instead of four, okay? Now, sometimes all the variables have the 53 00:02:53,105 --> 00:02:55,890 same set of values at the beginning. Okay? 54 00:02:55,890 --> 00:03:00,140 So this is what we see in this particular graph coloring example. 55 00:03:00,140 --> 00:03:05,380 At the beginning, I can use all the colors for actually, all these countries. 56 00:03:05,380 --> 00:03:08,505 Right? And so which one do I start first? 57 00:03:08,505 --> 00:03:10,830 Okay? Now I can say, oh I'm going to start with 58 00:03:10,830 --> 00:03:11,910 Denmark. Okay? 59 00:03:11,910 --> 00:03:15,480 But Denmark, in this particular case is easy. 60 00:03:15,480 --> 00:03:17,750 Right? So it only connected to Germany. 61 00:03:17,750 --> 00:03:20,522 So there is only one color that it won't be able to take and therefore, I don't 62 00:03:20,522 --> 00:03:23,294 want to start there because I'm going to give it a color that's going to remove a 63 00:03:23,294 --> 00:03:27,690 color from Germany. But that doesn't mean anything, right? 64 00:03:27,690 --> 00:03:30,923 So, what I have to start from is someplace which is essentially connected 65 00:03:30,923 --> 00:03:34,262 to many, many, many different countries, and that's where it's going to be the 66 00:03:34,262 --> 00:03:38,364 most difficult to color. In this particular case, guess which 67 00:03:38,364 --> 00:03:41,570 country it is, right? So, we'll start with Belgium, okay? 68 00:03:41,570 --> 00:03:44,485 For instance, okay, so I want to illustrate or sort of first-fail 69 00:03:44,485 --> 00:03:48,310 principle on a very interesting example. It's a puzzle. 70 00:03:48,310 --> 00:03:50,110 It's called the Euler Knight problem, okay? 71 00:03:50,110 --> 00:03:54,660 It's basically having a knight in chess, and making sure that you visit all the 72 00:03:54,660 --> 00:04:00,080 places in the chess board, and visit them exactly once, okay? 73 00:04:00,080 --> 00:04:02,140 Following the rules of chess. Okay? 74 00:04:02,140 --> 00:04:04,360 Now, its pretty tough to do but, that manually. 75 00:04:04,360 --> 00:04:07,020 I know only one girl who actually did it, did that. 76 00:04:07,020 --> 00:04:10,140 She was in a computer science class, computer architecture, you know, she was 77 00:04:10,140 --> 00:04:13,260 completely bored and so she was playing this thing during class and some point 78 00:04:13,260 --> 00:04:16,540 she said, yeah! And she found it, okay? 79 00:04:16,540 --> 00:04:18,868 So if you can't sleep at night, try this. It's not easy. 80 00:04:18,868 --> 00:04:20,748 Okay? Now, it's an interesting problem because 81 00:04:20,748 --> 00:04:23,240 it's connected to a lot of problems in routing. 82 00:04:23,240 --> 00:04:26,006 It's kind of an abstraction for these problems, okay? 83 00:04:26,006 --> 00:04:29,240 So, but essentially, what I want to show you is the first-fail principle on this 84 00:04:29,240 --> 00:04:32,740 particular example because it's very intriguing, okay? 85 00:04:32,740 --> 00:04:36,460 So this is the model. You see a very simple model for this. 86 00:04:36,460 --> 00:04:39,580 The decision variables are the jump variable, okay basically for every 87 00:04:39,580 --> 00:04:43,226 position in the chess board. Okay, you have to, you have to know where 88 00:04:43,226 --> 00:04:46,398 the knight is going to jump next. Okay, and so you are basically 64 89 00:04:46,398 --> 00:04:49,112 variable, one for every, you know, position on the chest board and that 90 00:04:49,112 --> 00:04:52,666 tells you where you jump next. Once you've those you can follow the path 91 00:04:52,666 --> 00:04:55,204 of the knight. Okay, and the only constraints that you 92 00:04:55,204 --> 00:04:59,059 have is that all these variables have to make up a circuit, okay? 93 00:04:59,059 --> 00:05:02,186 So, if you start from one place and follow this, this path, you're going to 94 00:05:02,186 --> 00:05:06,805 go back to exactly the same place, okay? And you will visit every position in the 95 00:05:06,805 --> 00:05:09,530 chess board exactly once. Okay? 96 00:05:09,530 --> 00:05:11,290 Now this is a tough constraint to implement. 97 00:05:11,290 --> 00:05:15,710 We can just think about it and we'll come back to that later on, okay? 98 00:05:15,710 --> 00:05:19,610 But this is essentially how the model is stated here. 99 00:05:19,610 --> 00:05:22,834 Now, one more thing that we have to do is we have to now basically specify for 100 00:05:22,834 --> 00:05:26,474 every position where the knight can jump, that follows basically the rules of chess 101 00:05:26,474 --> 00:05:31,577 and this is this boring set of positions that you see over there. 102 00:05:31,577 --> 00:05:35,009 you know don't try to spend your time understanding it, but you know you just 103 00:05:35,009 --> 00:05:39,314 have to know that this can be done, okay? Now what I want to show you is 104 00:05:39,314 --> 00:05:43,247 essentially how the first-fail principle is working on this particular example, 105 00:05:43,247 --> 00:05:46,100 okay? So let's look at the chess board. 106 00:05:46,100 --> 00:05:48,551 This is the chess board at the beginning, okay? 107 00:05:48,551 --> 00:05:50,650 So, where do we start? Okay? 108 00:05:50,650 --> 00:05:52,480 Are we starting at the middle? Are we starting here? 109 00:05:52,480 --> 00:05:54,310 Are we starting over there? Okay? 110 00:05:54,310 --> 00:05:56,590 Well, the first-fail principle is telling you. 111 00:05:56,590 --> 00:06:00,080 Start first where you are the most likely to fail. 112 00:06:00,080 --> 00:06:01,818 You know? Where are the position where it's 113 00:06:01,818 --> 00:06:04,620 difficult to actually, you know, jump, okay? 114 00:06:04,620 --> 00:06:08,460 Well, these are the corners, right? So when you look at this guy here, okay? 115 00:06:08,460 --> 00:06:10,800 There are only two position where we can jump. 116 00:06:10,800 --> 00:06:13,916 And as soon as it jumps to one. Okay, you know that the, you know, you 117 00:06:13,916 --> 00:06:18,030 know where the previous, you know where, essentially, the previous position was. 118 00:06:18,030 --> 00:06:19,988 Okay? So essentially, there are only two 119 00:06:19,988 --> 00:06:21,915 positions. And as soon as you choose one, you also 120 00:06:21,915 --> 00:06:24,240 fix the value of another variable's. Okay? 121 00:06:24,240 --> 00:06:27,199 That's where you're going to stop. These corners are tough, because there 122 00:06:27,199 --> 00:06:30,731 are only two places where they can jump. If you're in the middle, there are these 123 00:06:30,731 --> 00:06:33,190 eight places where you can jump. Many more positions. 124 00:06:33,190 --> 00:06:35,660 Okay? So, we know where to start. 125 00:06:35,660 --> 00:06:38,100 Okay? So, the key, the key question here is 126 00:06:38,100 --> 00:06:40,320 where do we go next? Okay? 127 00:06:40,320 --> 00:06:43,884 And every time you know, I, I've, I, I've been teaching a class on combinatorial 128 00:06:43,884 --> 00:06:48,390 optimization and ask this question. People always tell me, okay well you have 129 00:06:48,390 --> 00:06:51,875 to take this guy probably because it has very few positions. 130 00:06:51,875 --> 00:06:54,494 Okay? But this is not what the system is 131 00:06:54,494 --> 00:06:56,940 going to do. Once again, the system is going to look 132 00:06:56,940 --> 00:07:01,650 at all the position, and find out the one which is the toughest to assign. 133 00:07:01,650 --> 00:07:04,660 And where is that? Well, that's in the other corner, okay? 134 00:07:04,660 --> 00:07:06,500 Because, once again, there are only two position. 135 00:07:06,500 --> 00:07:09,461 Where for this guy, there are at least three or four positions, four for that 136 00:07:09,461 --> 00:07:12,812 particular one, okay? So, essentially, what's the system is 137 00:07:12,812 --> 00:07:16,096 going to do? Is built some small parts all over the, 138 00:07:16,096 --> 00:07:19,068 the places. And the constraint is essentially trained 139 00:07:19,068 --> 00:07:21,836 to make sure that you can connect them into a big circuit. 140 00:07:21,836 --> 00:07:24,136 Okay? At every, every stage and after every 141 00:07:24,136 --> 00:07:27,470 assignment. So this is a partial state of the system. 142 00:07:27,470 --> 00:07:30,590 You see we built a couple of interesting paths all over the place. 143 00:07:30,590 --> 00:07:32,568 Okay? And this is a solution at the end. 144 00:07:32,568 --> 00:07:34,850 Okay. Beautiful, right? 145 00:07:34,850 --> 00:07:37,826 And so this is what the first-fail principle is actually doing on the Euler 146 00:07:37,826 --> 00:07:41,980 Knight problem, finding the variables which are the toughest to assign. 147 00:07:41,980 --> 00:07:45,290 They have a small domain. That means that they are tough to assign, 148 00:07:45,290 --> 00:07:47,395 okay? So let's put this principle in 149 00:07:47,395 --> 00:07:50,567 perspective now and let's look how you program this search and how you can 150 00:07:50,567 --> 00:07:54,066 express them, okay? So I am going to start with the eight 151 00:07:54,066 --> 00:07:56,946 queens problems again so that I can illustrate a little bit how you write 152 00:07:56,946 --> 00:08:00,900 this search procedure. So what you see here at the bottom. 153 00:08:00,900 --> 00:08:03,090 Is a search procedure for the queens problem, okay? 154 00:08:03,090 --> 00:08:05,100 And there are various things that you can see there. 155 00:08:05,100 --> 00:08:07,952 So the first instruction is a for instruction, and basically it's telling 156 00:08:07,952 --> 00:08:10,730 the system iterate for every one of the queens. 157 00:08:10,730 --> 00:08:15,450 I want to assign a value to every queen, so I have to iterate over all the queens. 158 00:08:15,450 --> 00:08:18,439 The second instruction is actually pretty interesting, it's the try all 159 00:08:18,439 --> 00:08:21,428 instruction, and essentially that instruction is a non-deterministic 160 00:08:21,428 --> 00:08:25,460 instruction, it's not a loop. What it's trying to do, is to assign a 161 00:08:25,460 --> 00:08:28,554 value to the particular variable. It's to choose a value in a 162 00:08:28,554 --> 00:08:30,595 non-deterministic fashion in this particular case. 163 00:08:30,595 --> 00:08:32,838 Okay? Now it's going to try to do that, find 164 00:08:32,838 --> 00:08:35,876 one popular value. But he's not going to try them all at 165 00:08:35,876 --> 00:08:38,746 this point, okay? It's just going to pick a point, okay, in 166 00:08:38,746 --> 00:08:42,063 a non-deterministic fashion. And then execute whatever the body is 167 00:08:42,063 --> 00:08:43,810 below. Okay? 168 00:08:43,810 --> 00:08:47,650 But in, but if, if later on, okay, the execution fail, okay, it's going to come 169 00:08:47,650 --> 00:08:51,396 back to this instruction and try another one. 170 00:08:51,396 --> 00:08:54,644 Okay, so the for loop is kind of iterating over all the values, a try all 171 00:08:54,644 --> 00:08:58,284 knows that it has many possibilities to actually do something, and it's going to 172 00:08:58,284 --> 00:09:02,044 pick up one. And if later on you are, you know, 173 00:09:02,044 --> 00:09:04,648 basically in the failure mode, you're going to come back and try another one, 174 00:09:04,648 --> 00:09:07,690 okay? That's non-deterministic instruction. 175 00:09:07,690 --> 00:09:10,399 The last string that you see in this string is essentially, as soon as you, as 176 00:09:10,399 --> 00:09:13,151 you have a variable, you have selected a value for the variable, you are going to 177 00:09:13,151 --> 00:09:16,980 basically add a constraint to the constraint stock. 178 00:09:16,980 --> 00:09:21,110 Stating that that variable is basically assigned to that value, okay? 179 00:09:21,110 --> 00:09:24,295 So that's three component that we'll see in a lot of the search procedures that 180 00:09:24,295 --> 00:09:28,340 we're going to see in this lecture. You start by iterating over the variable, 181 00:09:28,340 --> 00:09:31,460 you non-deterministically choose a value for them, and you add a constraints 182 00:09:31,460 --> 00:09:35,904 inside a constraint store, okay? Remember the computational paradigm, 183 00:09:35,904 --> 00:09:37,765 okay? So what you have is basically a 184 00:09:37,765 --> 00:09:40,880 constraint store that's pruning the search base. 185 00:09:40,880 --> 00:09:44,210 And then a search, okay? What a search is doing is always adding 186 00:09:44,210 --> 00:09:47,490 constraint to the constraint store. Okay? 187 00:09:47,490 --> 00:09:50,618 The search is adding constraint to the constraint store and the constraint store 188 00:09:50,618 --> 00:09:55,220 is basically sending a razor back to the search saying okay, yeah, good. 189 00:09:55,220 --> 00:09:56,145 Success. Okay? 190 00:09:56,145 --> 00:09:59,458 Or sometimes you have the constraints and they say failure, okay? 191 00:09:59,458 --> 00:10:02,858 You, you can't satisfy your constraints, when something like that happens you go 192 00:10:02,858 --> 00:10:07,435 back to non-deterministic instruction, and try another value for the variable. 193 00:10:07,435 --> 00:10:10,778 Okay? So in a sense, what you need to do, is 194 00:10:10,778 --> 00:10:16,196 that every time a constraint fails, okay? So, you go back to a non-deterministic 195 00:10:16,196 --> 00:10:19,710 instruction and try a value which has not been tried again. 196 00:10:19,710 --> 00:10:21,400 Okay? If there is no possibility for that 197 00:10:21,400 --> 00:10:25,830 non-deterministic instruction, what you will do is go back to another one. 198 00:10:25,830 --> 00:10:29,460 That was, you know, the previous one, and try that and, and try another value for 199 00:10:29,460 --> 00:10:34,034 that non-deterministic instruction, okay? I'm going to go into, into, into the 200 00:10:34,034 --> 00:10:37,320 details of this a little bit more such that you see how basically the syntax 201 00:10:37,320 --> 00:10:42,445 corresponds to the semantics that I'm talking eh, talking about, okay? 202 00:10:42,445 --> 00:10:45,943 So when you look at the full instruction essentially what you are doing, you can 203 00:10:45,943 --> 00:10:50,295 view that, you can unfold this loop. And what you're really doing is do a 204 00:10:50,295 --> 00:10:53,265 bunch of try instruction for the first variable, for the second variable and so 205 00:10:53,265 --> 00:10:54,890 on. Okay? 206 00:10:54,890 --> 00:10:57,410 Now if at any point you fail for one of these, you're going to go back to the 207 00:10:57,410 --> 00:11:00,790 previous one and try another value. If that, if there are no values left, 208 00:11:00,790 --> 00:11:04,260 you're going to go back to the previous one, try another value and so on. 209 00:11:04,260 --> 00:11:06,704 That's what the system is doing, is basically, you know, 210 00:11:06,704 --> 00:11:10,080 non-deterministically selecting some of these values. 211 00:11:10,080 --> 00:11:13,344 If at some point you fail, you go back to the previous one and try another value 212 00:11:13,344 --> 00:11:16,498 for that one. If there are no one left, you go back one 213 00:11:16,498 --> 00:11:19,674 more level up, okay? So essentially that's what the system is 214 00:11:19,674 --> 00:11:22,340 doing there. Okay, for every queen, there will be this 215 00:11:22,340 --> 00:11:25,890 non-deterministic instruction and you are trying to see which values you can assign 216 00:11:25,890 --> 00:11:28,107 to that queen. Okay? 217 00:11:28,107 --> 00:11:32,663 Now, let's look a little bit into a, into more detail on how the trial instruction 218 00:11:32,663 --> 00:11:36,620 is working. It's a non-deterministic construction, 219 00:11:36,620 --> 00:11:39,050 which can potentially explore all the values. 220 00:11:39,050 --> 00:11:43,590 But it only does so when basically activated because of a failure, right? 221 00:11:43,590 --> 00:11:46,945 So in a sense, what you can do is this try all instruction is a big try 222 00:11:46,945 --> 00:11:51,154 instruction, okay, and which is basically telling you, oh try first the value one, 223 00:11:51,154 --> 00:11:57,460 the value two, the value three, and so on and so forth, okay? 224 00:11:57,460 --> 00:12:00,628 And in this particular case, if you fill for the value 1, okay, so if for instance 225 00:12:00,628 --> 00:12:03,556 the value 1, when you put it inside a constrained system, the constrained 226 00:12:03,556 --> 00:12:07,540 system is telling you oh, I have a failure. 227 00:12:07,540 --> 00:12:11,220 You will go and move to the next instruction in the try, okay? 228 00:12:11,220 --> 00:12:15,380 And try the second value, and so on and so forth, until you arrive at the bottom. 229 00:12:15,380 --> 00:12:18,857 If none of these values are actually successful, you will go back to a 230 00:12:18,857 --> 00:12:23,302 previous try all instruction. And select the next try in the list where 231 00:12:23,302 --> 00:12:26,899 you had left out. At the you know, at, at the previous 232 00:12:26,899 --> 00:12:29,950 execution of that try all. Okay? 233 00:12:29,950 --> 00:12:32,988 So, that's essentially what these try and follow you know, the way they are 234 00:12:32,988 --> 00:12:35,585 interacting, and the way non-deterministic computations are 235 00:12:35,585 --> 00:12:38,760 basically computed. Okay? 236 00:12:38,760 --> 00:12:41,486 So, what I want to talk about now, are the various ways you can use these 237 00:12:41,486 --> 00:12:45,828 primitive to do various kinds of search. And I'm going to talk about variable 238 00:12:45,828 --> 00:12:48,680 value ordering. Value variable labeling. 239 00:12:48,680 --> 00:12:50,180 Okay? I'm going to talk about domain splitting. 240 00:12:50,180 --> 00:12:54,070 I'm going to say how you can focus some of the search on the objective function. 241 00:12:54,070 --> 00:12:57,018 I'm going to talk about symmetry breaking during searching and randomization and 242 00:12:57,018 --> 00:12:58,870 restart. Okay? 243 00:12:58,870 --> 00:13:01,814 In this lecture, we'll do only the first one, which is basically variable and 244 00:13:01,814 --> 00:13:04,710 value labeling. We're also looking at the value of the 245 00:13:04,710 --> 00:13:08,095 objective function at the very end of the lecture. 246 00:13:08,095 --> 00:13:10,976 Okay? So variable value labeling are probably 247 00:13:10,976 --> 00:13:14,810 the most simple search procedure that you can design in a constraint programming 248 00:13:14,810 --> 00:13:18,424 system. It basically has two stamps, the first is 249 00:13:18,424 --> 00:13:22,240 you choose a variable that you want to assign and then you choose a value. 250 00:13:22,240 --> 00:13:25,168 The first step you have to reiterate for the valuable, the second step is a 251 00:13:25,168 --> 00:13:28,745 non-deterministic step. Now, once again, you want to apply the 252 00:13:28,745 --> 00:13:32,320 first-fail principal, which means that you want to find the ordering of these 253 00:13:32,320 --> 00:13:36,640 variables in a very, in a very, in a very specific way. 254 00:13:36,640 --> 00:13:39,648 You want to start with the one which have the toughest. 255 00:13:39,648 --> 00:13:44,554 Toughest to, to, to give a value to. And typically, you know, the size of the 256 00:13:44,554 --> 00:13:47,530 domain of the variable is going to be a good indicator of what is tough and what 257 00:13:47,530 --> 00:13:49,684 is not tough. Okay? 258 00:13:49,684 --> 00:13:52,846 The variable which has the smallest domain means that you have remove a lot 259 00:13:52,846 --> 00:13:56,302 of value from that variable. It means that it is probably interacting 260 00:13:56,302 --> 00:13:59,400 with a lot of other constraints. It's probably a variable which is very 261 00:13:59,400 --> 00:14:02,405 difficult to instantiate, okay, to give a value to. 262 00:14:02,405 --> 00:14:04,849 Okay? So the ordering that we will want in 263 00:14:04,849 --> 00:14:08,140 general is going to be dynamic. You just don't want to fix the ordering 264 00:14:08,140 --> 00:14:10,578 of this variable. You want to choose a variable which has 265 00:14:10,578 --> 00:14:13,482 the smallest domain, then you propagate all the constraints, that reduces the 266 00:14:13,482 --> 00:14:16,298 search space again and then now you want to look for the next variable with the 267 00:14:16,298 --> 00:14:19,170 smallest domain. Okay? 268 00:14:19,170 --> 00:14:22,206 And that variable may not be, it may not have been the second most attractive 269 00:14:22,206 --> 00:14:26,375 variable the first time around because now more values have been removed. 270 00:14:26,375 --> 00:14:28,510 Okay? So what you want to do is iterate this, 271 00:14:28,510 --> 00:14:30,874 you know? Choosing the variable with the smallest 272 00:14:30,874 --> 00:14:33,820 domain, propagating. Choosing the variable with the smallest 273 00:14:33,820 --> 00:14:36,919 domain, propagating, okay? And so this is essentially all you can do 274 00:14:36,919 --> 00:14:39,330 that in a, in a constraint programming system. 275 00:14:39,330 --> 00:14:42,270 The forward instruction, though, is capturing an order. 276 00:14:42,270 --> 00:14:46,350 And in this particular case, what I do is that I look at the variable, row r. 277 00:14:46,350 --> 00:14:50,646 And I take the size of its domain. And that basically tells me what, at this 278 00:14:50,646 --> 00:14:54,810 particular point in time, the domain size of that variable is. 279 00:14:54,810 --> 00:14:56,963 Okay? So, in a sense, you have to view this 280 00:14:56,963 --> 00:15:00,212 iteration now as look at all the variables, okay, which have not been 281 00:15:00,212 --> 00:15:04,652 given a value so far. Take the one which is the smallest 282 00:15:04,652 --> 00:15:07,370 domain, and execute the body. Okay? 283 00:15:07,370 --> 00:15:09,840 So take the variable which has the smallest domain, no? 284 00:15:09,840 --> 00:15:13,134 You execute the body. So which basically will assign a 285 00:15:13,134 --> 00:15:16,916 non-deterministic, will assign non-deterministically a value to that 286 00:15:16,916 --> 00:15:19,800 variable. Then you're going to go back to the loop 287 00:15:19,800 --> 00:15:22,545 and look at all the variables that you have not selected, you know, at this 288 00:15:22,545 --> 00:15:26,330 point, and take the one which has the smallest domain now. 289 00:15:26,330 --> 00:15:28,480 Okay? Why am I saying now? 290 00:15:28,480 --> 00:15:32,076 Because essentially the constraint that we added, it started constraint 291 00:15:32,076 --> 00:15:35,170 propagation in the constraint engine, okay? 292 00:15:35,170 --> 00:15:38,404 In the constraint propagation part of the system and has reduced the size of the 293 00:15:38,404 --> 00:15:41,102 domains, okay? So basically what you have to see 294 00:15:41,102 --> 00:15:44,092 compared to what we have seen before, what we are doing though, is choosing the 295 00:15:44,092 --> 00:15:48,530 order of variables that we're going to give value to in a dynamic fashion. 296 00:15:48,530 --> 00:15:53,740 Taking the one which has the smallest domain with every time, okay? 297 00:15:53,740 --> 00:15:56,820 So essentially what we are seeing is a two steps. 298 00:15:56,820 --> 00:15:59,686 First step is choosing the variable. And typically the variable which has the 299 00:15:59,686 --> 00:16:02,050 smallest domain. That's the first-fail principle. 300 00:16:02,050 --> 00:16:05,735 Know at any point in time, you may have several variables which have the smallest 301 00:16:05,735 --> 00:16:08,029 domain. Which one do you choose? 302 00:16:08,029 --> 00:16:10,570 Okay? One of the good principle that you have 303 00:16:10,570 --> 00:16:13,270 to try, that, that you can try to apply, is choose the one which is the most 304 00:16:13,270 --> 00:16:16,303 constrained. Remember the graph coloring at the 305 00:16:16,303 --> 00:16:19,405 beginning, all the variables, all the countries, have exactly the same color, 306 00:16:19,405 --> 00:16:21,460 possible colors. Okay? 307 00:16:21,460 --> 00:16:24,522 Which one did we choose? We chose a country which was connected to 308 00:16:24,522 --> 00:16:27,230 many other ones. It was very constrained. 309 00:16:27,230 --> 00:16:29,140 That's what we can do. Okay? 310 00:16:29,140 --> 00:16:32,170 Now, in the particular case of the queens problem, for instance. 311 00:16:32,170 --> 00:16:34,780 We can choose the queens which has the smallest domain. 312 00:16:34,780 --> 00:16:37,818 And if there are ties, we can choose the one which is as close as the middle of 313 00:16:37,818 --> 00:16:40,110 the board as possible. Why? 314 00:16:40,110 --> 00:16:43,404 Because when you place a queens in middle, it has a tendency to remove more 315 00:16:43,404 --> 00:16:48,095 values than when you place a queen on, on the sides of the chessboard. 316 00:16:48,095 --> 00:16:50,986 Okay, so how to do that well essentially this is easy you take the for all 317 00:16:50,986 --> 00:16:54,269 construction that you've seen before and know you're using a lexicographic you 318 00:16:54,269 --> 00:16:58,436 know criteria. You take the viable which is the smallest 319 00:16:58,436 --> 00:17:02,035 domain and in case of ties the one which is closer to the middle of the chest 320 00:17:02,035 --> 00:17:05,914 wall, okay? So, essentially, same thing as before 321 00:17:05,914 --> 00:17:09,398 except that now instead of choosing the value with one criterion, I'm basically 322 00:17:09,398 --> 00:17:13,658 using two criterion, okay? One starting with the smallest domain and 323 00:17:13,658 --> 00:17:16,645 then the variable which is the most constrained. 324 00:17:16,645 --> 00:17:19,741 Okay? Now remember also one of the things that 325 00:17:19,741 --> 00:17:23,389 we had on, on the, on the queens problem, was this dual modeling, where you had 326 00:17:23,389 --> 00:17:27,151 variable fold associated with a column, and then variable associated with the 327 00:17:27,151 --> 00:17:31,998 row, okay? Now, that's a good example to show how 328 00:17:31,998 --> 00:17:35,478 you can both choose a variable ordering in a dynamic fashion, and a value 329 00:17:35,478 --> 00:17:40,820 ordering in a dynamic fashion, okay? So what you see here, okay, is that we 330 00:17:40,820 --> 00:17:45,065 look at the raw variables as the one that we want to assign. 331 00:17:45,065 --> 00:17:48,298 Okay, and we choose the one which is the smallest domain and then we have to 332 00:17:48,298 --> 00:17:51,849 assign a value okay, and when we assign a value essentially this is equivalent is 333 00:17:51,849 --> 00:17:57,195 in giving a value to a color. So we can try the value in an authoring 334 00:17:57,195 --> 00:18:00,825 which is also the first-fail principle which says oh but choose the value which 335 00:18:00,825 --> 00:18:06,472 corresponds to the column variable which has the smallest domain because that. 336 00:18:06,472 --> 00:18:10,037 Column is thought to instantiate as well. And that's what you, that's what you are 337 00:18:10,037 --> 00:18:12,669 doing here okay? You choose a dynamic holder for the 338 00:18:12,669 --> 00:18:15,497 variables. Then you choose a dynamic holder for the 339 00:18:15,497 --> 00:18:18,245 values. In both cases, you're actually applying, 340 00:18:18,245 --> 00:18:22,813 you know, the first-fail principal, okay? So that's the kind of things that you can 341 00:18:22,813 --> 00:18:26,918 do in a constraint programming system. Choose a dynamic ordering for the 342 00:18:26,918 --> 00:18:29,855 variable. Choose a dynamic ordering for the values. 343 00:18:29,855 --> 00:18:33,713 A very interesting thing that you can do. Okay, so in general, okay so when you 344 00:18:33,713 --> 00:18:37,495 have a variable value labeling what you're going to do is to choose the most 345 00:18:37,495 --> 00:18:42,595 constrained variable, okay first. That basically means the smallest domain 346 00:18:42,595 --> 00:18:45,722 of the variable that fails very often. Okay that's the kind of things that you 347 00:18:45,722 --> 00:18:48,050 want to do. And the value ordering is going to be 348 00:18:48,050 --> 00:18:50,890 generally a little bit different. What you want to do is try to maximize 349 00:18:50,890 --> 00:18:55,138 the probability of finding a solution. So we're going to try to value which 350 00:18:55,138 --> 00:18:59,310 actually leaves as many options as possible in the future. 351 00:18:59,310 --> 00:19:01,950 Okay? Because that helps you find a solution. 352 00:19:01,950 --> 00:19:05,636 You leave flexibility for the variables. So in a sense here we are trying to find, 353 00:19:05,636 --> 00:19:09,464 trying to, you know, look at the region which is the toughest, but also trying to 354 00:19:09,464 --> 00:19:14,246 find a feasible solutions. of course, sometimes this is, you know, 355 00:19:14,246 --> 00:19:17,098 this is just a heuristic, this is not, you know, a rule that you have to apply 356 00:19:17,098 --> 00:19:19,996 generally, but this is typically something which is useful in practice, in 357 00:19:19,996 --> 00:19:24,380 many, in many applications. Okay? 358 00:19:24,380 --> 00:19:28,230 So essentially, what, what I've shown you so far is that in constraint programming, 359 00:19:28,230 --> 00:19:33,290 most of the time, okay, we try to use feasibility information for branching. 360 00:19:33,290 --> 00:19:34,766 And why? Because that's essentially what a 361 00:19:34,766 --> 00:19:37,765 constraint programming system is doing. It's basically reasoning about 362 00:19:37,765 --> 00:19:40,915 feasibility, pruning the search base, and that gives you a lot of information about 363 00:19:40,915 --> 00:19:43,615 which variables are tough, which variables are central to actually the 364 00:19:43,615 --> 00:19:48,764 problem that we are trying to solve. But sometimes we have an optimization 365 00:19:48,764 --> 00:19:51,279 problem and it's very. So you're trying to find an optimal 366 00:19:51,279 --> 00:19:53,903 solution for an objective function and it's important to look at the value of 367 00:19:53,903 --> 00:19:57,560 the objective function as well. Okay now as I told you before, when we 368 00:19:57,560 --> 00:20:00,521 start the optimization problem now the optimization function becomes the 369 00:20:00,521 --> 00:20:03,510 constraints. Every time you find a solution. 370 00:20:03,510 --> 00:20:06,518 So either we use this search base, sort of, the feasible information is still 371 00:20:06,518 --> 00:20:09,704 very important. But we can do it better than just 372 00:20:09,704 --> 00:20:14,577 exploiting the feasible information. I also, you know, reasoning about the 373 00:20:14,577 --> 00:20:18,330 objective function itself. And what I want to do now is illustrate 374 00:20:18,330 --> 00:20:22,564 that on a very interesting problem. And which is generally very challenging 375 00:20:22,564 --> 00:20:26,588 for optimization system. And constraint programming is really nice 376 00:20:26,588 --> 00:20:29,658 for solving these problems. So it's called Serializable Data 377 00:20:29,658 --> 00:20:33,024 Services, and it's essentially implementing protocol that gives you that 378 00:20:33,024 --> 00:20:37,415 gives you software which is reliable. Okay so this is something that we did 379 00:20:37,415 --> 00:20:40,899 with some colleagues at UConn, and the protocol that we were trying to implement 380 00:20:40,899 --> 00:20:44,529 is called eventually serialized data services. 381 00:20:44,529 --> 00:20:47,649 And the way to think about this is that you have a set of components, okay, 382 00:20:47,649 --> 00:20:52,730 software components that you have to map on a set of hard, on a set of machines. 383 00:20:52,730 --> 00:20:55,785 So a set a set of hardware, okay, and what you do, and, and, and to do that, 384 00:20:55,785 --> 00:20:58,746 you have to satisfy some reliability conditions so there will be different 385 00:20:58,746 --> 00:21:01,942 components that have to be located on the same machine, some components that have 386 00:21:01,942 --> 00:21:07,594 to be located on different machine. But you want this protocol to be as 387 00:21:07,594 --> 00:21:10,474 efficient as possible so you want basically to minimize the traffic the 388 00:21:10,474 --> 00:21:14,900 communication traffic between these various, various component. 389 00:21:14,900 --> 00:21:17,140 If you place them on different machine, its going to cost you more to accurately 390 00:21:17,140 --> 00:21:20,710 exchange data between them. Okay, so to, so when you formalize this 391 00:21:20,710 --> 00:21:24,940 problem, okay in a mathematical programming sense. 392 00:21:24,940 --> 00:21:28,390 It become what is called a generalized quadratic assignment problem. 393 00:21:28,390 --> 00:21:31,370 So, this is the data that you have. You have a communication frequency 394 00:21:31,370 --> 00:21:34,331 matrices which tells you how much two components are interacting with each 395 00:21:34,331 --> 00:21:38,090 other. That's the, the data f. 396 00:21:38,090 --> 00:21:42,378 You have a, a, a matrix which tells you the distance between the various hardware 397 00:21:42,378 --> 00:21:47,740 components this is a distance matrix. H, okay, its essentially the number of 398 00:21:47,740 --> 00:21:52,263 hops that you have to do from you're moving from one hallway to another one. 399 00:21:52,263 --> 00:21:55,503 Then the decision variables are going to be this vector x and x is going to tell 400 00:21:55,503 --> 00:21:59,229 you for every component on which hardware that particular software components is 401 00:21:59,229 --> 00:22:03,504 going to be placed. And c is a set of components and then you 402 00:22:03,504 --> 00:22:06,880 have two types of constraints. You have the colocation constraints and 403 00:22:06,880 --> 00:22:09,694 the separation constraints. The separation constraints are telling 404 00:22:09,694 --> 00:22:11,860 you that two components cannot be on the same machine. 405 00:22:11,860 --> 00:22:14,700 If they are you know, the, the protocol wouldn't be reliable. 406 00:22:14,700 --> 00:22:16,932 And then you have these colocation constraints just saying the opposite, 407 00:22:16,932 --> 00:22:19,750 these two things have to be on the same machine. 408 00:22:19,750 --> 00:22:23,740 And the objective function is going to be minimizing the traffic in the network. 409 00:22:23,740 --> 00:22:26,974 So you have the frequency matrix that you see there, and then you have the number 410 00:22:26,974 --> 00:22:30,670 of hops and Xa and Xb are basically the decision variables. 411 00:22:30,670 --> 00:22:34,010 It's where do you place component a, where do you place component b? 412 00:22:34,010 --> 00:22:37,060 And what you are trying to do is to minimize the communication between all 413 00:22:37,060 --> 00:22:40,312 the components, okay? And that, of course, depends on how much 414 00:22:40,312 --> 00:22:43,304 they communicate, and how far away from each other they are basically placed ins, 415 00:22:43,304 --> 00:22:47,950 on, on the, on the hardware. So this is the model, okay? 416 00:22:47,950 --> 00:22:50,920 This is the model that we have for this partical, these, these generalized, 417 00:22:50,920 --> 00:22:54,857 quadratic assignment problem. Okay, the model is essentially a 418 00:22:54,857 --> 00:22:59,370 straightforward implementation of what I just presented on the next slide. 419 00:22:59,370 --> 00:23:02,406 You see the objective function, which is a direct translation of the objective 420 00:23:02,406 --> 00:23:05,040 function that you saw on the previous slide. 421 00:23:05,040 --> 00:23:07,846 You see the matrix H there, H Matrix, index by two variables, so that's the 422 00:23:07,846 --> 00:23:11,780 element constraint that we saw a couple of lecture back. 423 00:23:11,780 --> 00:23:14,965 Then what you see, the two types of constraints, the colocation constraints, 424 00:23:14,965 --> 00:23:18,199 which are basically telling that, you know, two components in, which have to be 425 00:23:18,199 --> 00:23:22,610 colocated have this, are assigned to the same component. 426 00:23:22,610 --> 00:23:25,370 And then for the separation constraints, what you have is basically all different 427 00:23:25,370 --> 00:23:28,521 constraint. What is really interesting in this 428 00:23:28,521 --> 00:23:31,510 particular example is the search procedure, because it's going to focus on 429 00:23:31,510 --> 00:23:34,830 the objective function. So this is what you do. 430 00:23:34,830 --> 00:23:38,193 At every step, until all of the components have been placed, you will 431 00:23:38,193 --> 00:23:41,969 take a component i, which is interact, which has not been assigned so far, and 432 00:23:41,969 --> 00:23:47,020 which is interacting with as many components as possible. 433 00:23:47,020 --> 00:23:51,442 It is a very high, essentially, it is a very high communication um,it maximized 434 00:23:51,442 --> 00:23:55,650 the communication with another component, okay? 435 00:23:55,650 --> 00:23:59,269 So that's what you see there. Select i which is the maximum frequency 436 00:23:59,269 --> 00:24:03,190 of communication with another component chain. 437 00:24:03,190 --> 00:24:05,170 Why do you want to focus on that particular component? 438 00:24:05,170 --> 00:24:08,998 Because its interacting heavily with somebody else and therefore it will have 439 00:24:08,998 --> 00:24:13,500 a big effect on the objective function once you place it, okay? 440 00:24:13,500 --> 00:24:15,400 And therefore, that's why you want to focus on this one. 441 00:24:15,400 --> 00:24:19,065 You will gain a lot of information as soon as you place that component. 442 00:24:19,065 --> 00:24:22,045 Okay? The way you will place it, is obviously, 443 00:24:22,045 --> 00:24:25,675 by trying to make sure that you don't make this objective function increase too 444 00:24:25,675 --> 00:24:29,609 much. You basically want to find a value, such 445 00:24:29,609 --> 00:24:33,341 that you minimize. The communication, the number of hops 446 00:24:33,341 --> 00:24:37,502 with respect to the other components that it, that it's interacting with, okay, and 447 00:24:37,502 --> 00:24:41,658 that's what you see in this particular instruction. 448 00:24:41,658 --> 00:24:45,840 And then you assign the particular component to that particular location. 449 00:24:45,840 --> 00:24:48,940 So in a sense what is important here is that you are using information on the 450 00:24:48,940 --> 00:24:52,242 objective function. To drive the search, and this is a 451 00:24:52,242 --> 00:24:55,996 critical aspect on this problem. If you don't do that, essentially the, 452 00:24:55,996 --> 00:25:00,580 the execution time is going to increase by an order of magnitude, okay? 453 00:25:00,580 --> 00:25:02,880 So let me try to summarize what we have seen in this lecture. 454 00:25:02,880 --> 00:25:06,431 What we have seen is a, a one type of, of search procedure which is very frequently 455 00:25:06,431 --> 00:25:10,490 used in practice, it's called variable labeling procedure. 456 00:25:10,490 --> 00:25:14,290 We saw the first-fail principal, which tells you to try first. 457 00:25:14,290 --> 00:25:18,780 When its very, where, where it's hot. Okay, where you are most likely to fail. 458 00:25:18,780 --> 00:25:22,044 And that's, you know a first-fail principle typically is using feasibility 459 00:25:22,044 --> 00:25:25,940 information you know, which variables have the smallest domain. 460 00:25:25,940 --> 00:25:28,873 But, it can also use information from the objective function. 461 00:25:28,873 --> 00:25:31,849 By looking at which components are difficult to place, and would increase 462 00:25:31,849 --> 00:25:35,065 the objective function which would make some of the other constraints much more 463 00:25:35,065 --> 00:25:39,670 difficult to, to satisfy, okay? So we'll more sophisticated search 464 00:25:39,670 --> 00:25:43,002 procedure during the next lecture, but this gives you a first taste on what you 465 00:25:43,002 --> 00:25:46,130 can do in a constraint programming system. 466 00:25:46,130 --> 00:25:47,210 Thank you.