1 00:00:00,320 --> 00:00:03,175 Welcome back. This is discrete optimization, again and 2 00:00:03,175 --> 00:00:07,165 we are moving to the second computational part for optimization which is called 3 00:00:07,165 --> 00:00:11,490 local search. This is the outline for today. 4 00:00:11,490 --> 00:00:14,499 We're going to start with basic interaction to our local search, and then 5 00:00:14,499 --> 00:00:19,280 we'll cover very simple local search, which is called max/min conflict. 6 00:00:19,280 --> 00:00:22,382 To introduce most of the concepts that we will be dealing with in the next couple 7 00:00:22,382 --> 00:00:25,539 of lectures. So, a couple of years ago when my son 8 00:00:25,539 --> 00:00:31,120 was, you know, very young, so I gave him the eight queens problem to solve, okay? 9 00:00:31,120 --> 00:00:33,450 So I wanted to see how he would just approach it. 10 00:00:33,450 --> 00:00:36,663 And so this is what he did, he took all these queens, okay, that I gave him, and 11 00:00:36,663 --> 00:00:40,180 he put them on the chess board. Okay? 12 00:00:40,180 --> 00:00:42,660 And then what he did was started moving these queens. 13 00:00:42,660 --> 00:00:44,390 Okay? Trying to find a configuration where none 14 00:00:44,390 --> 00:00:46,651 of the queens were attacking each other. Okay? 15 00:00:46,651 --> 00:00:50,363 So, he didn't try to prove the search space, or try to extend you know, a 16 00:00:50,363 --> 00:00:54,640 partial solution. He just moved the queens around. 17 00:00:54,640 --> 00:00:57,710 And this is exactly what local search is about. 18 00:00:57,710 --> 00:01:00,846 So, what you're going to do is you're going to move from configuration to 19 00:01:00,846 --> 00:01:05,319 configuration, by doing local moves. So, moving the configuration from it's 20 00:01:05,319 --> 00:01:08,658 current state to a state which is very close to it, but you know, but changing 21 00:01:08,658 --> 00:01:12,204 it a little bit. In the hope of getting closer to a 22 00:01:12,204 --> 00:01:14,460 particular solution. Okay? 23 00:01:14,460 --> 00:01:19,014 So local search, okay, is basically working on complete assignments of values 24 00:01:19,014 --> 00:01:23,361 to the decision variables and then essentially is modifying those, those, 25 00:01:23,361 --> 00:01:27,190 those assignments. Okay? 26 00:01:27,190 --> 00:01:29,460 So is there a different from constraint programming? 27 00:01:29,460 --> 00:01:32,452 Well, essentially, what we were doing, we're working with partial assignments, 28 00:01:32,452 --> 00:01:35,270 and trying to see if we could extend them. 29 00:01:35,270 --> 00:01:38,214 And, to make sure that we could extend them, we were trying to prune the search 30 00:01:38,214 --> 00:01:41,020 base as much as possible so that we would not try to extend them with a value 31 00:01:41,020 --> 00:01:46,820 which, which was not feasible. Local search is way more brutal, okay? 32 00:01:46,820 --> 00:01:49,960 So we accept that we're going to violate some of these constraints. 33 00:01:49,960 --> 00:01:55,144 And then we just try to eliminate those, those, those, those violations as we 34 00:01:55,144 --> 00:01:58,804 proceed, okay? So, how to drive a local search, okay, 35 00:01:58,804 --> 00:02:01,450 there will be different things that we can do, okay? 36 00:02:01,450 --> 00:02:04,400 And it depends essentially on the nature of the problem. 37 00:02:04,400 --> 00:02:07,281 If you have a satisfaction problem, what you will do is you will always start with 38 00:02:07,281 --> 00:02:10,674 an invisible configuration. Otherwise you would have already a 39 00:02:10,674 --> 00:02:13,040 solution and therefore there would be no problem to solve. 40 00:02:13,040 --> 00:02:15,849 And then what we are going to do is start, you know, move from this 41 00:02:15,849 --> 00:02:20,180 infeasible, you know, configuration toward, you know, feasibility. 42 00:02:20,180 --> 00:02:24,272 And trying to essentially make this configuration more and more, less and 43 00:02:24,272 --> 00:02:28,268 less infeasible in a sense. in pure optimization problems the only 44 00:02:28,268 --> 00:02:31,300 thing that you have is an objective function, you have no constraints. 45 00:02:31,300 --> 00:02:34,372 Okay, and what you are trying to do is essentially go to the optimal solution, 46 00:02:34,372 --> 00:02:39,880 so you start with a sub-optimal solution. A local search is going to try to move 47 00:02:39,880 --> 00:02:44,466 progressively towards optimality. And then, you have constrained 48 00:02:44,466 --> 00:02:47,213 optimization problems which are the most complicated, of course, you have both 49 00:02:47,213 --> 00:02:51,210 constraints and optimization. And I will review some of the options 50 00:02:51,210 --> 00:02:55,790 later on, once we have seen above satisfaction and optimization problems. 51 00:02:55,790 --> 00:02:59,318 Because there are many ways to actually try to address those problems in low 52 00:02:59,318 --> 00:03:01,101 consumption. Okay? 53 00:03:01,101 --> 00:03:05,021 Now lets look at satisfaction problems first and how to drive the search towards 54 00:03:05,021 --> 00:03:08,674 feasibility. And the key idea here is essentially we 55 00:03:08,674 --> 00:03:11,846 have this, you know feasible, well this satisfaction problem and we will 56 00:03:11,846 --> 00:03:14,810 transform it into a sequence of optimization, into an optimization 57 00:03:14,810 --> 00:03:17,194 problem. Okay? 58 00:03:17,194 --> 00:03:21,447 So we use the concept of violation. Essentially, at any point, we have that 59 00:03:21,447 --> 00:03:24,372 configuration. Okay, basically this assignments of 60 00:03:24,372 --> 00:03:28,229 values to the decision variables. And we know that their are a bunch of 61 00:03:28,229 --> 00:03:31,250 constraints that are not, that are violated, okay? 62 00:03:31,250 --> 00:03:34,470 We can count them, for instance. And then what we can try to, and this is 63 00:03:34,470 --> 00:03:37,720 only one of the ways to do it, but we can try to minimize the number of violations 64 00:03:37,720 --> 00:03:41,966 to these constraints. So we want to move from a configuration 65 00:03:41,966 --> 00:03:45,560 to another configuration where there are fewer violations. 66 00:03:45,560 --> 00:03:48,080 Okay? Now how do we do that? 67 00:03:48,080 --> 00:03:50,490 Well we have to decide what is a local move. 68 00:03:50,490 --> 00:03:54,054 And once again, and we'll see that in the next couple of lectures, there are many 69 00:03:54,054 --> 00:03:58,020 ways you can move from one configuration to the next. 70 00:03:58,020 --> 00:04:02,160 The simple things is just to select a decision variable and change its value. 71 00:04:02,160 --> 00:04:04,235 Okay? So very simple move. 72 00:04:04,235 --> 00:04:07,057 Okay? Now once you have defined all moves that 73 00:04:07,057 --> 00:04:10,193 you can take, you have to design the one that you're really going to select and 74 00:04:10,193 --> 00:04:12,010 execute. Okay? 75 00:04:12,010 --> 00:04:15,178 And once again there are many choices, and we'll see many different strategies 76 00:04:15,178 --> 00:04:18,900 over the next couple of lectures. But the thing that we are going to do, 77 00:04:18,900 --> 00:04:23,470 the, the approach we are going to pursue today is simply a maximum conflict. 78 00:04:23,470 --> 00:04:27,088 approach which is essentially a slight generalization of the main conflict 79 00:04:27,088 --> 00:04:30,166 heuristic , which has been very successful in a variety of problems, 80 00:04:30,166 --> 00:04:33,825 okay? So what is the max/min conflict heuristic 81 00:04:33,825 --> 00:04:36,429 doing? Essentially what we do, is choose a 82 00:04:36,429 --> 00:04:40,320 variable that appear in the large numbers of violations. 83 00:04:40,320 --> 00:04:44,330 So, we look at the variable which, which is really violating a lot. 84 00:04:44,330 --> 00:04:47,270 All those variables really violating a lot of constraints. 85 00:04:47,270 --> 00:04:50,609 And then what we try to do is to change the value of that constraint so that you 86 00:04:50,609 --> 00:04:53,930 decrease the number of violations the most. 87 00:04:53,930 --> 00:04:56,060 Okay? So, let me just trade that. 88 00:04:56,060 --> 00:04:59,234 Okay, so this is remember this is the constraint programming model for the, the 89 00:04:59,234 --> 00:05:02,106 queens problem. And what is interesting to see on that 90 00:05:02,106 --> 00:05:06,120 particular model are all the constraints that you see over there, right. 91 00:05:06,120 --> 00:05:09,288 So, some of these constraints, once you assign some value to the variables, are 92 00:05:09,288 --> 00:05:13,050 going to be violated, are the ones are going to be satisfied, okay. 93 00:05:13,050 --> 00:05:15,510 Now visually, this is what this looks like, right, so when you look at the 94 00:05:15,510 --> 00:05:18,390 part, so you see. You see here, you know there will be a 95 00:05:18,390 --> 00:05:21,640 constraint which is violated. This is another constraint which is 96 00:05:21,640 --> 00:05:24,359 violated, okay? So now when we look at the max/min 97 00:05:24,359 --> 00:05:27,722 [UNKNOWN], what we want to do first is to compute, you know, the various 98 00:05:27,722 --> 00:05:31,484 violations, the constraint violations in which are the particular variables 99 00:05:31,484 --> 00:05:35,946 appear, okay? So we look at this particular queen here 100 00:05:35,946 --> 00:05:39,326 and now we look at the constraints that they are violating and, of course, what 101 00:05:39,326 --> 00:05:42,394 we have to do is to look at, you know, the vertical, the diagonals and the 102 00:05:42,394 --> 00:05:47,616 horizontal lines, okay? So in this particular case, we see that 103 00:05:47,616 --> 00:05:51,390 this particular variable appear in exactly one conflict, right? 104 00:05:51,390 --> 00:05:53,410 This queen is attacking that one. Okay? 105 00:05:53,410 --> 00:05:56,695 So we move to the second one, okay, second queen. 106 00:05:56,695 --> 00:06:00,721 Okay, and what we see there is that this queen attacks that queen, and it attacks 107 00:06:00,721 --> 00:06:05,760 this one, and so this particular queen appears in two violations. 108 00:06:05,760 --> 00:06:08,417 Okay? And we can do that for all the Queens. 109 00:06:08,417 --> 00:06:12,906 So this is another queen which is basically having two violation. 110 00:06:12,906 --> 00:06:17,580 The next one is very aggressive has three violation, and so on and so forth. 111 00:06:17,580 --> 00:06:21,548 And so essentially what you see here are all the vi, the violations that these 112 00:06:21,548 --> 00:06:25,640 variables, appear ins, ins, into, and what the number that you see over here 113 00:06:25,640 --> 00:06:31,970 essentially is the total number of constraints that are violated, okay? 114 00:06:31,970 --> 00:06:34,566 Now, the first thing that a maximum conflict heuristic will do is take a 115 00:06:34,566 --> 00:06:37,675 queen which appear in the largest number of violation. 116 00:06:37,675 --> 00:06:39,790 Okay? So you have a queen here which is very 117 00:06:39,790 --> 00:06:42,140 aggressive and appearing at three violations. 118 00:06:42,140 --> 00:06:43,395 That's the queen that you're going to select. 119 00:06:43,395 --> 00:06:45,080 Okay? So that's the first step. 120 00:06:45,080 --> 00:06:48,008 Now we have the queen that we really want to move because this queen is very 121 00:06:48,008 --> 00:06:49,620 aggressive. Okay? 122 00:06:49,620 --> 00:06:52,726 So what do we do? So now we have to choose the value that 123 00:06:52,726 --> 00:06:55,530 we going to to assign to that particular queen. 124 00:06:55,530 --> 00:06:59,064 And what we can do is decide, okay so what happens if I move this queen to that 125 00:06:59,064 --> 00:07:04,220 particular position, okay how does that change the constraint violation? 126 00:07:04,220 --> 00:07:06,948 And what you can see in this particular case is that instead of having three 127 00:07:06,948 --> 00:07:10,835 violations, we would have only two, so we are attacking these two queens. 128 00:07:10,835 --> 00:07:13,230 And then you can do the same thing for the next queen. 129 00:07:13,230 --> 00:07:16,404 Here in this particular case the queen is still very aggressive and has still three 130 00:07:16,404 --> 00:07:20,069 viola, three violations, okay? And then we continue doing this 131 00:07:20,069 --> 00:07:25,064 essentially for everyone of the possible position for that part of the queens. 132 00:07:25,064 --> 00:07:28,214 Okay, and what we see at that point is that, you know, if you want to reduce the 133 00:07:28,214 --> 00:07:31,314 violation the most we have to choose one of these values and we can randomly 134 00:07:31,314 --> 00:07:36,373 choose, let's say the first one here. Okay, and at that point what we do is we 135 00:07:36,373 --> 00:07:40,640 place the queens at that particular position, so that's the local move. 136 00:07:40,640 --> 00:07:43,415 We chose the queens. We chose a new position for the queens 137 00:07:43,415 --> 00:07:47,400 and we you know, we performed the move. Okay? 138 00:07:47,400 --> 00:07:49,938 So at that point we have a new configuration and we can redo all the 139 00:07:49,938 --> 00:07:53,425 computations that we have done. We can find that there are five 140 00:07:53,425 --> 00:07:56,626 violations overall. We can find the number of violations in 141 00:07:56,626 --> 00:07:59,580 which all the queens are participating to. 142 00:07:59,580 --> 00:08:03,090 And then we can decide, you know, we can select the queen. 143 00:08:03,090 --> 00:08:06,456 One of the queens participating in the most violation and start deciding where 144 00:08:06,456 --> 00:08:09,334 to move it. In this particular case only one of the, 145 00:08:09,334 --> 00:08:12,310 of the move is going to decrease the number of violation, so that is where we 146 00:08:12,310 --> 00:08:16,090 move the queens. We have a new configuration, so what do 147 00:08:16,090 --> 00:08:17,930 we do? Exactly the same thing. 148 00:08:17,930 --> 00:08:20,788 Now we have four violation. We reduce the number of violation by one. 149 00:08:20,788 --> 00:08:24,088 We recompute the violation so the variables, you know, we select the one 150 00:08:24,088 --> 00:08:27,663 which appears in the most violation, and we start moving it again at a position 151 00:08:27,663 --> 00:08:31,770 that will decrease the number of violations. 152 00:08:31,770 --> 00:08:35,720 And we keep doing this, now we have, we move another queen. 153 00:08:35,720 --> 00:08:40,426 And we can, we have three violations now. We continue moving this queen again, we 154 00:08:40,426 --> 00:08:43,633 have another queen which has two violations. 155 00:08:43,633 --> 00:08:46,260 We move, we decrease the violation by one. 156 00:08:46,260 --> 00:08:49,856 We keep doing this, another queen which is violated by one, we decrease the 157 00:08:49,856 --> 00:08:53,510 violation to one, and then finally we will be able to reduce the violation to 158 00:08:53,510 --> 00:08:58,170 zero, and we have a feasible solution. OK? 159 00:08:58,170 --> 00:09:01,866 So what is important to see here is that essentially we start from an infeasible 160 00:09:01,866 --> 00:09:05,983 configuration which has a number of constraint violations. 161 00:09:05,983 --> 00:09:09,343 And we try to move to, you know, configuration which have fewer and fewer 162 00:09:09,343 --> 00:09:12,850 violations. And at every step, we try to do that by 163 00:09:12,850 --> 00:09:16,252 selecting a queens, in this particular case, which, which is, you know, 164 00:09:16,252 --> 00:09:19,654 appearing in the largest number of violation, and moving it to a place which 165 00:09:19,654 --> 00:09:25,204 decrease the violation the most. This is just one of the possible 166 00:09:25,204 --> 00:09:27,701 strategies. We'll see many strategies in the next 167 00:09:27,701 --> 00:09:31,169 couple of lecture but this is essentially illustrating the concept behind local 168 00:09:31,169 --> 00:09:33,485 search. Okay? 169 00:09:33,485 --> 00:09:38,264 So so in a sense the way to think about local search is that you have an 170 00:09:38,264 --> 00:09:41,880 optimization function. Okay? 171 00:09:41,880 --> 00:09:45,080 That the, an objective function that you are trying to optimize. 172 00:09:45,080 --> 00:09:48,741 And then what the local moves are doing is defining a neighborhood. 173 00:09:48,741 --> 00:09:52,413 That's essentially the configurations that are close to the configuration that 174 00:09:52,413 --> 00:09:56,410 we are considering right now, okay? So, in the sense that the neighborhood 175 00:09:56,410 --> 00:09:58,930 is, from a particular configuration, it's going to give you a set of 176 00:09:58,930 --> 00:10:03,420 configurations. And that's the places where we can move. 177 00:10:03,420 --> 00:10:05,150 Okay? So, in the particular example of the 178 00:10:05,150 --> 00:10:08,286 queens problems, the neighboring configurations were simply the ones that 179 00:10:08,286 --> 00:10:11,373 you can reach by selecting the, one of the queens which is most violated, and 180 00:10:11,373 --> 00:10:16,195 moving it to a position which decreased the violation the most. 181 00:10:16,195 --> 00:10:18,878 Okay? So, in a sense you can think of local 182 00:10:18,878 --> 00:10:22,392 search as a graph exploration. You start, you know, from a particular 183 00:10:22,392 --> 00:10:25,428 point, and then you start moving to configuration, to another configuration, 184 00:10:25,428 --> 00:10:28,853 and so on. And you try to go to configuration which 185 00:10:28,853 --> 00:10:31,855 are, you know, more and more feasible in a sense. 186 00:10:31,855 --> 00:10:34,130 Okay? So that's what we do. 187 00:10:34,130 --> 00:10:36,139 Okay? So the concept, the key, the key concept 188 00:10:36,139 --> 00:10:39,100 in local search is the concept of local minima. 189 00:10:39,100 --> 00:10:40,830 Okay? That's what a local search does. 190 00:10:40,830 --> 00:10:43,570 It gets you a local minima. And what is the local minima? 191 00:10:43,570 --> 00:10:46,758 It's a state. Inside the configuration space where, 192 00:10:46,758 --> 00:10:50,230 wherever you move, wherever you're neighbors are, okay, they are going to be 193 00:10:50,230 --> 00:10:54,553 worse off than where you are. So it's a position where when you look at 194 00:10:54,553 --> 00:10:57,460 every neighbor N okay, to the configuration C that you are conf, that 195 00:10:57,460 --> 00:11:00,724 you are considering right now, the value of that objective functions of that 196 00:11:00,724 --> 00:11:06,870 neighbor is going to be greater than the current value of the objective function. 197 00:11:06,870 --> 00:11:09,080 Okay? So essentially. 198 00:11:09,080 --> 00:11:11,832 You know, you are at that point, wherever you move, you are going to get worse, or 199 00:11:11,832 --> 00:11:14,825 at best, you know, as, as good as you are right now. 200 00:11:14,825 --> 00:11:17,790 Okay? So in a sense, the local search that you 201 00:11:17,790 --> 00:11:20,650 know, the, the basic kernel of a local search, is going to select a 202 00:11:20,650 --> 00:11:25,190 configuration seed, initially, using some method. 203 00:11:25,190 --> 00:11:29,030 Then compute the neighborhood, okay. So that's a set of the configurations. 204 00:11:29,030 --> 00:11:32,432 Well if you've got a computer set I of all the neighbors that you can, that you 205 00:11:32,432 --> 00:11:37,890 can reach, and which are better than the configurations that you are in right now. 206 00:11:37,890 --> 00:11:41,103 So we look at essentially all the neighbors which are basically decreasing 207 00:11:41,103 --> 00:11:43,890 the value of the objective function, okay? 208 00:11:43,890 --> 00:11:47,858 If that set is not empty you select one of these configurations, apply it, and 209 00:11:47,858 --> 00:11:53,129 then you recompute the set of configuration in which you can move to. 210 00:11:53,129 --> 00:11:55,421 Okay? So basically, you know, local search is 211 00:11:55,421 --> 00:11:59,261 this kind of iteration where you move from one position to a better position, 212 00:11:59,261 --> 00:12:03,963 and you keep doing that until you reach a local minima. 213 00:12:03,963 --> 00:12:06,091 Okay? So local search, you know, gives you no 214 00:12:06,091 --> 00:12:08,587 guarantees. Okay, so the only thing that it's 215 00:12:08,587 --> 00:12:11,915 going to give you is a local minima, that local minima can be arbitrarily bad, or 216 00:12:11,915 --> 00:12:15,731 arbitrarily good. Okay, so one of the things that we'll see 217 00:12:15,731 --> 00:12:19,059 in a lot of the lectures later on is how to escape this local minima, or to try to 218 00:12:19,059 --> 00:12:22,780 find local minima that are of high quality. 219 00:12:22,780 --> 00:12:27,064 Not getting stuck into a poor quality optima and there are many, many ways to 220 00:12:27,064 --> 00:12:30,907 do this, and but we'll talk about this later on once we have seen many of the 221 00:12:30,907 --> 00:12:37,349 concept behind local search in itself. So for the moment we'll do this greedy 222 00:12:37,349 --> 00:12:40,681 local such algorithm, which always trying to improve and gets stuck at some point 223 00:12:40,681 --> 00:12:44,890 in a local minima. Afterwards, we'll see how to escape. 224 00:12:44,890 --> 00:12:47,571 Okay? Now in satisfactions in satisfaction 225 00:12:47,571 --> 00:12:51,993 problems what we saw is that the function F is actually minimizing the number of 226 00:12:51,993 --> 00:12:55,247 constraint violations. Okay? 227 00:12:55,247 --> 00:12:59,153 And usually when this function reaches zero, we know that we have a feasible 228 00:12:59,153 --> 00:13:02,528 solution. If we get stuck in a local minima, which 229 00:13:02,528 --> 00:13:05,370 is a value higher than zero, you know, the solution that we found is not 230 00:13:05,370 --> 00:13:09,064 feasible. It's, the configuration that we found is 231 00:13:09,064 --> 00:13:11,303 not a feasible solution. Okay? 232 00:13:11,303 --> 00:13:15,180 So, there are many ways to measure this constraint violation. 233 00:13:15,180 --> 00:13:17,889 And once again, this is a topic that we will return to, but what we have done so 234 00:13:17,889 --> 00:13:20,211 far is basically looking at the constraints, and deciding if the 235 00:13:20,211 --> 00:13:25,264 constraints is violated or not. There are other ways to actually measure 236 00:13:25,264 --> 00:13:28,012 these violations. You can consider how violated that 237 00:13:28,012 --> 00:13:31,160 constraint is, and we'll talk about that later on as well. 238 00:13:32,410 --> 00:13:35,644 and the variable variations that we actually studied in this, in the, in the 239 00:13:35,644 --> 00:13:38,682 examples in the queens example, we're essentially counting the number of 240 00:13:38,682 --> 00:13:43,125 constraints. That were violated and that the variables 241 00:13:43,125 --> 00:13:48,532 were, was participating into. So that's essentially the basic 242 00:13:48,532 --> 00:13:51,995 introduction to local search. We're going to go into more and more 243 00:13:51,995 --> 00:13:56,752 details in the next couple of lectures. Thank you.