1 00:00:00,110 --> 00:00:03,060 this could optimization local search, part two. 2 00:00:03,060 --> 00:00:08,730 more concept and the main concept today is going to be the concept of swaps. 3 00:00:08,730 --> 00:00:12,062 But there will be another set of really interesting concepts on the way you'll 4 00:00:12,062 --> 00:00:15,235 see that. So let me start again with the car 5 00:00:15,235 --> 00:00:18,172 sequencing example. You'll remember these beautiful cars, 6 00:00:18,172 --> 00:00:20,604 right? So basically what we have is an assembly 7 00:00:20,604 --> 00:00:24,006 line we have to produce these cars from this assembly line but these cars are 8 00:00:24,006 --> 00:00:27,462 requiring different types of options right so leather seats, moon roofs all 9 00:00:27,462 --> 00:00:32,790 these kind of things. So when you produce this car as we saw 10 00:00:32,790 --> 00:00:36,341 previously you have to basically sequence them on the assemnly line in such a way 11 00:00:36,341 --> 00:00:41,420 that the production unit Have the time to put the options on the cars. 12 00:00:41,420 --> 00:00:43,986 Okay? So how, how do you do that is really the 13 00:00:43,986 --> 00:00:47,400 question here. Okay, that's what we have to solve. 14 00:00:47,400 --> 00:00:50,951 We have to sequence these cars such that production unit will have the time to put 15 00:00:50,951 --> 00:00:53,640 the options on the car. Okay? 16 00:00:53,640 --> 00:00:56,384 So this is a configuration. This is a solution acitvity that we saw 17 00:00:56,384 --> 00:00:58,912 before. You know every one of the roads you see 18 00:00:58,912 --> 00:01:02,050 over here okay so that's the capacity constraints. 19 00:01:02,050 --> 00:01:05,832 That about the eruption lets say [UNKNOWN] and the capacity of that one is 20 00:01:05,832 --> 00:01:09,862 one out of two which basically means if you take two successive slots you can at 21 00:01:09,862 --> 00:01:13,520 most one one cause requiring interruptions otherwise the production 22 00:01:13,520 --> 00:01:17,364 won't have the time to actually put the options on the table on the On the, on 23 00:01:17,364 --> 00:01:23,478 the car. So so when we look at this thing from a, 24 00:01:23,478 --> 00:01:27,600 from a local search standpoint, what are we looking at? 25 00:01:27,600 --> 00:01:30,370 While we, what we'll do is we start with a sequence, right? 26 00:01:30,370 --> 00:01:34,400 We always seq start with, with configurations and that configuration may 27 00:01:34,400 --> 00:01:38,679 be completely violating these capacity constraints, okay? 28 00:01:39,710 --> 00:01:42,901 That's the way local search works. And what we're going to do here is, we're 29 00:01:42,901 --> 00:01:45,910 going to look at that configuration and we're going to look at 2, 2, 2 parts of 30 00:01:45,910 --> 00:01:51,245 the assembly line and we're going to swap them, okay so that's the basic idea here. 31 00:01:51,245 --> 00:01:53,147 Okay? So we're going to take two 32 00:01:53,147 --> 00:01:57,318 configurations, you know 2 types of [UNKNOWN] and we are going to swap that. 33 00:01:57,318 --> 00:01:59,260 Swap that. Okay? 34 00:01:59,260 --> 00:02:03,930 So, the first strategy therefore, is going to find a car configuration. 35 00:02:03,930 --> 00:02:06,130 Okay? Which appear in some violations, that 36 00:02:06,130 --> 00:02:09,610 means that some of the capacity constraints or maybe several will be, 37 00:02:09,610 --> 00:02:13,450 will be violated and what we will do is to swap that particular type of car with 38 00:02:13,450 --> 00:02:18,180 another car in the assembly line. Okay? 39 00:02:18,180 --> 00:02:21,970 And the goal of course, is going to be trying to minimize the violation. 40 00:02:21,970 --> 00:02:24,060 Okay? So, every one of these moves. 41 00:02:24,060 --> 00:02:27,780 Its goal will be mining, minimizing the overall violation of the capacity 42 00:02:27,780 --> 00:02:29,490 constraints. Okay? 43 00:02:29,490 --> 00:02:31,660 So let me illustrate that on an example, okay. 44 00:02:31,660 --> 00:02:36,012 So what you see here are all the, all of the assembly line that, the exact way we 45 00:02:36,012 --> 00:02:41,562 saw it for constraint programming. The, the diagram on the bottom, there, is 46 00:02:41,562 --> 00:02:45,390 essentially looking at all the options, and that's How we will be able to look at 47 00:02:45,390 --> 00:02:49,222 the violations. Now, the table that you see here, okay, 48 00:02:49,222 --> 00:02:52,450 is basically the various configurations that we have produced. 49 00:02:52,450 --> 00:02:54,925 I won't talk about it very much, because you'll see everything here. 50 00:02:54,925 --> 00:02:56,916 Here. So the beauty of local search is that at 51 00:02:56,916 --> 00:02:59,652 every point you see the everything because you've assigned you know 52 00:02:59,652 --> 00:03:03,470 essentially all the, all the, all the decision variables. 53 00:03:03,470 --> 00:03:06,834 Okay so what you see here is that we produce the various types of car you 54 00:03:06,834 --> 00:03:10,314 know, we had a demand for 1 for this one, 1 for that one, 2 for the you know to 55 00:03:10,314 --> 00:03:16,692 that 3rd type of car and so on. And so essentially what you see there is 56 00:03:16,692 --> 00:03:21,770 basically a completely arbitrary configurations at the beginning, Okay? 57 00:03:21,770 --> 00:03:24,605 Now we look at the options of that car and that's the kind of options that they 58 00:03:24,605 --> 00:03:27,641 require, okay? So you see for instance that here, you 59 00:03:27,641 --> 00:03:30,701 know, we have three cars requirirng option one, okay and we know that the 60 00:03:30,701 --> 00:03:35,360 capavity is one out of two so they will be violations there. 61 00:03:35,360 --> 00:03:37,984 Okay, and you see all the other options being required by the various types of 62 00:03:37,984 --> 00:03:40,676 cards. Okay so now we have to find we have to 63 00:03:40,676 --> 00:03:43,820 understand the concept of iteration right. 64 00:03:43,820 --> 00:03:46,828 So these capacity constraints are huge stuff right so they look at the entire 65 00:03:46,828 --> 00:03:49,355 line. But there is a very, very nice way of 66 00:03:49,355 --> 00:03:53,480 actually capturing the violation. What you do, is that we know the capacity 67 00:03:53,480 --> 00:03:56,910 of this guy is one out of two. So what we are going to do what you see 68 00:03:56,910 --> 00:04:00,447 there, right. We are going to take this window, this 69 00:04:00,447 --> 00:04:04,120 sliding window of two slot of a time, okay. 70 00:04:04,120 --> 00:04:08,404 And then we are going to look if inside that window, there is a violation or not, 71 00:04:08,404 --> 00:04:11,310 okay. So in this part of the case, we see a 72 00:04:11,310 --> 00:04:14,140 nice, you know. Two slot window. 73 00:04:14,140 --> 00:04:18,600 Only one carries, requiring the option so we're know that we are fine. 74 00:04:18,600 --> 00:04:21,274 Okay? So for the next for the next option, just 75 00:04:21,274 --> 00:04:25,332 a little bit complicated. Here my hand is probably not big enough 76 00:04:25,332 --> 00:04:30,587 but we have a window of three slots. And we are looking if there are more than 77 00:04:30,587 --> 00:04:33,850 two cars actually requesting that option, OK? 78 00:04:33,850 --> 00:04:37,468 So we can do that for essentially all the various options there, really big at the 79 00:04:37,468 --> 00:04:42,553 end because they're windows of size five. So in a sense, what we can do is we can 80 00:04:42,553 --> 00:04:46,975 take these windows and move them along the slot, the assembly line essentially 81 00:04:46,975 --> 00:04:51,397 And so you see this nice you know, window which is moving and at every step, okay, 82 00:04:51,397 --> 00:04:55,685 what we are doing there is looking how many cars are requesting that option in 83 00:04:55,685 --> 00:05:00,174 that particular window, and if there are more than one is this particular case we 84 00:05:00,174 --> 00:05:08,905 will have a violation. So essentially the violations are 85 00:05:08,905 --> 00:05:12,640 going to come when you are in a particular window okay? 86 00:05:12,640 --> 00:05:17,228 We are, the window is in a particular part of the assembly line such that the 87 00:05:17,228 --> 00:05:22,130 capacity of the production unit is violated, okay? 88 00:05:22,130 --> 00:05:25,230 So in this particular case what you see here is that it's violated so we know 89 00:05:25,230 --> 00:05:29,180 that we have one violation. We move it a little bit. 90 00:05:29,180 --> 00:05:32,648 to the right and we see another violation and then the last slot of the, the last 91 00:05:32,648 --> 00:05:36,065 two slot of the assembly lines have also two cars there requesting that option so 92 00:05:36,065 --> 00:05:42,370 we know that we have another violation. So, in this particular case, we know that 93 00:05:42,370 --> 00:05:46,790 the first, the capacity constraints of the the first option is violated three 94 00:05:46,790 --> 00:05:50,754 times, okay? Now, we can do that in a very similar 95 00:05:50,754 --> 00:05:55,389 fashion for the second option, okay? So also, you know, show which cars are 96 00:05:55,389 --> 00:05:57,720 here. Which, which options are basically 97 00:05:57,720 --> 00:06:01,110 violating the capacity constraints. We could do it for the next one, and we 98 00:06:01,110 --> 00:06:04,770 see that in this particular case we have two, we left two violations. 99 00:06:04,770 --> 00:06:06,740 Okay? And that's what you see there. 100 00:06:06,740 --> 00:06:09,867 And we also see which essentially slots are violating that particular 101 00:06:09,867 --> 00:06:11,390 constraints. Okay? 102 00:06:11,390 --> 00:06:13,750 And we can do that for every one of the lines. 103 00:06:13,750 --> 00:06:17,234 And you see. You know in this particular example, how 104 00:06:17,234 --> 00:06:20,732 many of the, the, the capacity constraints and, and how much the 105 00:06:20,732 --> 00:06:25,405 capacity constraints are violated. Okay. 106 00:06:25,405 --> 00:06:29,965 So the, the, look and such, no It's basically going to take configurations 107 00:06:29,965 --> 00:06:34,677 here, okay, types of cars, which are appearing in some violation, and then 108 00:06:34,677 --> 00:06:40,189 swap them together. Okay, so we take one, we take another one 109 00:06:40,189 --> 00:06:44,410 we swap them together we observe the two costs and obviously we have to [UNKNOWN] 110 00:06:44,410 --> 00:06:48,190 all of the violation and which of the slots inside the assembly lines Are 111 00:06:48,190 --> 00:06:54,480 basically in valuations. Okay, so we did, we did one move. 112 00:06:54,480 --> 00:06:57,299 This is another move. We take the, we take care two and car 10 113 00:06:57,299 --> 00:07:00,886 and sub them together. And we reduce the valuations again, so 114 00:07:00,886 --> 00:07:05,040 there is at least at this point, there is only one tiny violation. 115 00:07:05,040 --> 00:07:08,122 And we could continue doing things like this, and in this particular case we keep 116 00:07:08,122 --> 00:07:11,826 one violation and we can continue. These are the various local moves that 117 00:07:11,826 --> 00:07:15,609 you can do, okay? So, the key point here, is that compared 118 00:07:15,609 --> 00:07:21,760 to the queens example, what we are really doing Is swapping cars. 119 00:07:21,760 --> 00:07:24,880 We are not assigning a value to a particular to a particular to a 120 00:07:24,880 --> 00:07:28,920 particular to a partiuclar slot. So why do we do that? 121 00:07:28,920 --> 00:07:31,718 Think about it. Why are we essentiallyy considering 122 00:07:31,718 --> 00:07:36,390 swaps, and not assignments of values to the decision variables? 123 00:07:36,390 --> 00:07:40,342 Okay can you think about it? So the reason we are doing that is that 124 00:07:40,342 --> 00:07:44,310 we are automatically by doing that maintaining the satisfaction of one type 125 00:07:44,310 --> 00:07:50,063 of constraints, the demand constraints. So we are making sure that at any point 126 00:07:50,063 --> 00:07:53,370 the demand constraints is always satisfied. 127 00:07:53,370 --> 00:07:57,132 We always produce The right amount of cap So that constraint, we can just forget 128 00:07:57,132 --> 00:07:58,720 about it. Okay? 129 00:07:58,720 --> 00:08:02,185 So because we at all the first, the first, you know the first configurations 130 00:08:02,185 --> 00:08:05,485 that we had at all the cars that we needed to produce, once we swap, we keep 131 00:08:05,485 --> 00:08:09,225 exactly the same number of constraints, and the demand constraints is going to be 132 00:08:09,225 --> 00:08:13,420 satisfied forever. Right? 133 00:08:13,420 --> 00:08:16,299 So this is the key aspect here. So, in a sense, you know if you tried to 134 00:08:16,299 --> 00:08:19,420 abstract this a little bit, what we have is two types of constraints. 135 00:08:19,420 --> 00:08:22,780 There are the hard constraints, they're the constraints that you want [INAUDIBLE] 136 00:08:22,780 --> 00:08:25,564 of search procedure to satisfy all the time, and then you have the soft 137 00:08:25,564 --> 00:08:28,780 constraints, which are very nice because you can violate them and try to violate 138 00:08:28,780 --> 00:08:31,870 them less and less. Okay? 139 00:08:31,870 --> 00:08:34,660 So the key idea here is that in many of these complex problems, what you do is 140 00:08:34,660 --> 00:08:37,360 you separate the two constraints into the hard constraints and the soft 141 00:08:37,360 --> 00:08:41,090 constraints. You maintain the hard constraints. 142 00:08:41,090 --> 00:08:44,654 They are always satisfied by the local search and then the soft constraints can 143 00:08:44,654 --> 00:08:48,164 be violated and used trying to decrease the number of violations of these soft 144 00:08:48,164 --> 00:08:52,364 constraints. That's the basic power line here, when 145 00:08:52,364 --> 00:08:55,670 you try to solve satisfaction problems, okay? 146 00:08:55,670 --> 00:08:57,940 So let me move to another problem that we saw. 147 00:08:57,940 --> 00:09:01,460 And discuss how we can actually solve it wit local search again. 148 00:09:01,460 --> 00:09:05,413 This is a magic square where we trying to have this a square and trying to pit all 149 00:09:05,413 --> 00:09:09,425 different numbers into the various square such that the sum of the diagonals, the 150 00:09:09,425 --> 00:09:15,430 sum of the horizontal line, the rows and the and the columns. 151 00:09:15,430 --> 00:09:18,399 Were equal to the same number. So this other constraint that you saw 152 00:09:18,399 --> 00:09:21,682 okay, and essentially they constrainting that all the, the rows and the column, 153 00:09:21,682 --> 00:09:24,818 have to sum to t, and then you have the sum of diagonals, and once again you have 154 00:09:24,818 --> 00:09:28,052 to sum to t, and then you have the all different constraints, which is basically 155 00:09:28,052 --> 00:09:31,629 specifying that every one of the squares in the big square have to have received a 156 00:09:31,629 --> 00:09:36,950 different number. Okay? 157 00:09:36,950 --> 00:09:39,500 So, once again, we're going to do exactly the same thing. 158 00:09:39,500 --> 00:09:42,460 We're going to split these constraints into two sects. 159 00:09:42,460 --> 00:09:46,040 A hard constraint and then a bunch of soft constraints. 160 00:09:46,040 --> 00:09:48,970 So, the hard constraints here is going to be the all different constraints. 161 00:09:48,970 --> 00:09:52,426 Now, I'm going to make sure that we only assign different numbers to every one of 162 00:09:52,426 --> 00:09:56,420 the squares. Okay, the slot in the squares, in the 163 00:09:56,420 --> 00:09:58,930 square. And the other constraints, essentially 164 00:09:58,930 --> 00:10:02,080 here the inequalities, the equalities for the rows, the column, and the diagonals, 165 00:10:02,080 --> 00:10:06,284 are going to be soft constraints. We can violate them, and we'll move 166 00:10:06,284 --> 00:10:10,020 towards decreasing these violations. Okay. 167 00:10:10,020 --> 00:10:12,910 So, you know this is a particular configuration that we have. 168 00:10:12,910 --> 00:10:16,100 Look all the numbers here are different. Okay? 169 00:10:16,100 --> 00:10:19,220 And what we are trying to do is making sure that the you know, the rows, the 170 00:10:19,220 --> 00:10:23,180 rows, the columns and the diagonals sum to the same value. 171 00:10:23,180 --> 00:10:25,310 Okay? Now, the real magic number that we want 172 00:10:25,310 --> 00:10:27,060 to find here is 15. Okay? 173 00:10:27,060 --> 00:10:30,771 But we see that this particular column here sums to 17. 174 00:10:30,771 --> 00:10:33,870 [SOUND] You know, violation. Okay, that constraint is violating. 175 00:10:33,870 --> 00:10:38,180 This one is summing to 14, it's also violating, we have another violation. 176 00:10:38,180 --> 00:10:41,720 This constraint is also violating. I mean the whole thing here is violating. 177 00:10:41,720 --> 00:10:44,807 We are in a completely you know terrible state so we are not satisfying any of 178 00:10:44,807 --> 00:10:47,670 these constraints. OK? 179 00:10:47,670 --> 00:10:51,102 So, since we have these hard constraints, you know which is keeping all of these 180 00:10:51,102 --> 00:10:53,160 numbers different. OK? 181 00:10:53,160 --> 00:10:56,104 What we're going to do is, basically, look at, again, at the swapped neighbor 182 00:10:56,104 --> 00:10:58,488 root. We're going to take 2 positions in the 183 00:10:58,488 --> 00:11:02,454 square and going to swap the values. And we're going to look at the effect on 184 00:11:02,454 --> 00:11:05,636 the violation. So, now if we swap 8 and 3, what's going 185 00:11:05,636 --> 00:11:08,620 to happen? Is that, you know, the sum of the rows 186 00:11:08,620 --> 00:11:12,240 and the columns and so on? And the diagonals are going to change? 187 00:11:12,240 --> 00:11:16,410 But in this particular case all the constraints are violated again, okay. 188 00:11:16,410 --> 00:11:19,560 Now, when you look at this you say, this is a nice neighborhood, this is a nice 189 00:11:19,560 --> 00:11:23,574 way of modelling the problem. But every time I swap, you know, most of 190 00:11:23,574 --> 00:11:26,670 these constraints are going to still be violated. 191 00:11:26,670 --> 00:11:31,059 And therefore I get essentially no information, right. 192 00:11:31,059 --> 00:11:36,230 So in a sense I have nothing, nothing at all to drive my search, OK? 193 00:11:36,230 --> 00:11:42,510 So that's where essentially you can think of another way of representing violation. 194 00:11:42,510 --> 00:11:47,724 Instead of you know having this kind of mannequin approach, its I have violated 195 00:11:47,724 --> 00:11:49,770 or not. OK? 196 00:11:49,770 --> 00:11:54,080 So what you can do is to look at how much These constrains are violating. 197 00:11:54,080 --> 00:11:56,570 Is, is this constraint violating a lot, or not? 198 00:11:56,570 --> 00:11:59,580 Am I getting closer to the right value, or not? 199 00:11:59,580 --> 00:12:02,962 Okay, so that's what we're going to do. Because if we only look at the zero and 200 00:12:02,962 --> 00:12:07,178 one values, essentially We don't have enough information to actually drive this 201 00:12:07,178 --> 00:12:11,060 search, okay? So what is, what is, what is, you know 202 00:12:11,060 --> 00:12:14,150 what is the amout of violations of an equality? 203 00:12:14,150 --> 00:12:16,773 Well, if you look at the value of the left hand side, you look at the value of 204 00:12:16,773 --> 00:12:19,439 the right hand side, you take the difference between them and the absolute 205 00:12:19,439 --> 00:12:23,180 value, okay? So once you do that, you get a sense of 206 00:12:23,180 --> 00:12:28,024 how much that constraints it's violating. An therefore, you know, when you make a 207 00:12:28,024 --> 00:12:30,880 local move you can see that the violations of these constraints are 208 00:12:30,880 --> 00:12:34,170 actually decreasing. Instead of saying yes or no, you have 209 00:12:34,170 --> 00:12:36,530 something that tells you, yeah, yeah, yeah, yeah, yeah, you are making 210 00:12:36,530 --> 00:12:39,560 progress. An that's what we are going to use, okay. 211 00:12:39,560 --> 00:12:43,010 So once again, you know, the magic number that we want to get is 15. 212 00:12:43,010 --> 00:12:46,060 You see all the numbers here, you know for all the variations. 213 00:12:46,060 --> 00:12:50,140 But now the goal is not to find out you know, is this [UNKNOWN] satisfy enough. 214 00:12:50,140 --> 00:12:53,860 Is the, the basic idea is that can I get closer to 15 for everyone one of these 215 00:12:53,860 --> 00:12:57,628 rules verbally? Okay, so you see that here, you know, for 216 00:12:57,628 --> 00:13:00,892 that particular value, 17, the distance with respect to 15 is 2, so I have, you 217 00:13:00,892 --> 00:13:06,030 know, the degree of violation here is 2. Okay, so you look at the next one, 14, 218 00:13:06,030 --> 00:13:09,350 the distance to 15 is 1, so you have one violation. 219 00:13:09,350 --> 00:13:12,298 So when you look at everything here, you know, you see, essentially, the various 220 00:13:12,298 --> 00:13:15,280 violations. Of the various constraints. 221 00:13:15,280 --> 00:13:20,480 And you have a much finer measure on the hole close this configuration is a part 222 00:13:20,480 --> 00:13:25,654 of a feasible solution, OK? So the number of violations here while 223 00:13:25,654 --> 00:13:28,982 they're not to the degree, the order of the degree of violation is 21, when you 224 00:13:28,982 --> 00:13:32,520 swap these two guys know what happens, OK? 225 00:13:32,520 --> 00:13:37,410 So you can see that You have decreased the overall number of violations. 226 00:13:37,410 --> 00:13:39,520 It's 14 at this point. Okay? 227 00:13:39,520 --> 00:13:43,296 So in a sense, and this constraint is satisfied, okay, so there is zero degree 228 00:13:43,296 --> 00:13:47,260 of violation. But, overall you can see also that the 229 00:13:47,260 --> 00:13:50,860 various degree of violation of all the constraints. 230 00:13:50,860 --> 00:13:53,720 You know you see how these degrees are basically evolving. 231 00:13:53,720 --> 00:13:58,155 And so your goal now is to not minimize the number of violations but minimize. 232 00:13:58,155 --> 00:14:02,080 The overall degree of violation of the entire system. 233 00:14:02,080 --> 00:14:04,510 So different, but giving you more information. 234 00:14:04,510 --> 00:14:06,662 Okay. So we keep swapping, we swap 7 and 4 235 00:14:06,662 --> 00:14:10,556 here, and we decrease the total number, the total degree of violation to 5, so we 236 00:14:10,556 --> 00:14:14,791 get closer, closer. Okay, so we keep, you know, solving 8 and 237 00:14:14,791 --> 00:14:17,799 7, and then magically, okay, wow, that's a good name for this problem, right, 238 00:14:17,799 --> 00:14:21,155 magically, we solve the magic square problem. 239 00:14:21,155 --> 00:14:24,375 Okay, no violation anywhere. And we have a solutions. 240 00:14:24,375 --> 00:14:28,092 Okay, so the two key ideas that you see here is, once again, okay, so we look at 241 00:14:28,092 --> 00:14:33,750 this problem and we identify some hard constraints and some soft constraints. 242 00:14:33,750 --> 00:14:36,918 Okay, the hard constraints here is that all the digits Have to be different, and 243 00:14:36,918 --> 00:14:40,059 we maintain that. By swapping them, we don't change the 244 00:14:40,059 --> 00:14:43,000 number of digits or the nature of these digits, okay. 245 00:14:43,000 --> 00:14:46,675 So that's how we do a swap neighborhood. We maintain automatically one of the 246 00:14:46,675 --> 00:14:49,480 constraints, it's always going to be feasable. 247 00:14:49,480 --> 00:14:52,504 And then a second idea here, which was improtant, is that we sometimes don't 248 00:14:52,504 --> 00:14:56,480 want just to resolve about whether a constraint is violated or not. 249 00:14:56,480 --> 00:14:59,408 We want to find out how much is violated, and that's what we use for actually 250 00:14:59,408 --> 00:15:02,170 solving this problem. Okay? 251 00:15:02,170 --> 00:15:06,850 So, we'll see you next time. And talking about optimization. 252 00:15:06,850 --> 00:15:09,340 Look and search for pure optimization products. 253 00:15:09,340 --> 00:15:10,160 Thank you.