1 00:00:00,220 --> 00:00:04,048 So, welcome back, so this is Local Search Part IV, and we are not yet there, there 2 00:00:04,048 --> 00:00:08,530 are many more, but this lecture is really interesting. 3 00:00:08,530 --> 00:00:11,566 And the reason it's interesting is that we're going to look at optimization under 4 00:00:11,566 --> 00:00:15,180 constraints and how we can do local search on this. 5 00:00:15,180 --> 00:00:18,730 And why is it interesting, because there are many, many, many options. 6 00:00:18,730 --> 00:00:21,233 There are many ways you can actually approach this. 7 00:00:21,233 --> 00:00:24,026 And, and there will be different trade-offs in the complexity of the 8 00:00:24,026 --> 00:00:27,407 neighborhood and the complexity of the objective function, the complexity of the 9 00:00:27,407 --> 00:00:30,912 search. So we're going to illustrate every one of 10 00:00:30,912 --> 00:00:35,103 these, these, these various possibilities using graph coloring. 11 00:00:35,103 --> 00:00:39,047 Which is very simple to conceptually, but it's a very, very hard problem, in, in to 12 00:00:39,047 --> 00:00:43,275 solve very large instances. Remember, you know, graph coloring, this 13 00:00:43,275 --> 00:00:46,411 was the city of Europe that we saw when we were doing constraint programming, 14 00:00:46,411 --> 00:00:49,680 okay? So we can model that as a graph, right? 15 00:00:49,680 --> 00:00:54,508 So every country would be essentially a, associated with a vertex, and then there 16 00:00:54,508 --> 00:00:59,347 will be an edge between these two, these two vertices. 17 00:00:59,347 --> 00:01:03,837 If the two countries are adjacent, okay? And know that the, the goal of the 18 00:01:03,837 --> 00:01:07,558 application would be to find a coloring of this graph, such that every two 19 00:01:07,558 --> 00:01:12,820 vertices which are adjacent are given a different color, okay? 20 00:01:12,820 --> 00:01:17,430 So that's graph coloring at a high level. Now this is a tiny, tiny, tiny little 21 00:01:17,430 --> 00:01:19,995 graph. So what we are really going to be talking 22 00:01:19,995 --> 00:01:26,140 about here are really huge graphs, okay? So this is two 250 vertices. 23 00:01:26,140 --> 00:01:31,354 It's er a graph which has generated randomly, and the probability of having 24 00:01:31,354 --> 00:01:37,540 an edge between two vertices is is, is 10%, s, is .1, okay? 25 00:01:37,540 --> 00:01:40,560 And the key, and so you see, can already see how dense it is, okay? 26 00:01:40,560 --> 00:01:43,305 And one of the key things about graph coloring which is nice is that random 27 00:01:43,305 --> 00:01:46,503 products are typically very hard. So if you take, let's say, you know 250 28 00:01:46,503 --> 00:01:49,280 vertices, you know, .5 density, that's a really difficult problem, okay? 29 00:01:49,280 --> 00:01:54,990 So this is the kind of things that we want to tackle, okay? 30 00:01:54,990 --> 00:01:59,840 So, color me this graph, and finally the smallest number of colors, okay? 31 00:01:59,840 --> 00:02:03,750 To color this graph, okay? So there are two aspects of course. 32 00:02:03,750 --> 00:02:08,079 so one aspect is that we have to minimize this number of colors, okay? 33 00:02:08,079 --> 00:02:11,190 We want to as few as few colors as possible,but there is also the 34 00:02:11,190 --> 00:02:14,974 feasibility access. At any point we want this coloring to be 35 00:02:14,974 --> 00:02:18,508 legal, two counts, two nodes, two vertices that are basically adjacent to 36 00:02:18,508 --> 00:02:22,270 each other should be given a different color. 37 00:02:22,270 --> 00:02:25,042 So you know there is a trade off between these things and how we're going to deal 38 00:02:25,042 --> 00:02:28,015 with them, okay? And that's essentially the topic of this 39 00:02:28,015 --> 00:02:30,214 lecture. How can we balance the fact that we want 40 00:02:30,214 --> 00:02:33,175 to decrease the number of colors but we want also to get a feasible solution, 41 00:02:33,175 --> 00:02:36,044 okay? And so essentially the way we're going to 42 00:02:36,044 --> 00:02:39,430 combine that in, in Local search, there are basically three ways. 43 00:02:39,430 --> 00:02:42,730 The first one is just to say, you know, what I love in life are feasibility 44 00:02:42,730 --> 00:02:45,464 problems. So I want to reduce that problem to a 45 00:02:45,464 --> 00:02:48,561 sequence of feasibility problems. I only want to solve feasibility 46 00:02:48,561 --> 00:02:51,852 problems. And I will show you how to do that, okay? 47 00:02:51,852 --> 00:02:55,128 Then the other things, and this is essentially what we have done already for 48 00:02:55,128 --> 00:02:59,980 the traveling salesman problems and also for the where else is location. 49 00:02:59,980 --> 00:03:04,400 We, we can decide that we will stay in the space of feasible solution. 50 00:03:04,400 --> 00:03:09,291 We will only look at legal colorings, so no violations of the constraints, ever, 51 00:03:09,291 --> 00:03:12,090 okay? And you'll see that this is actually 52 00:03:12,090 --> 00:03:15,264 raising some interesting challenges, and, and we'll see how we can address some of 53 00:03:15,264 --> 00:03:18,675 them, okay? So, then essentially, the last thing is 54 00:03:18,675 --> 00:03:22,926 like, well, I don't want to look at this as a feasibility problem, okay? 55 00:03:22,926 --> 00:03:26,070 Because it's both a feasibility and optimization problem. 56 00:03:26,070 --> 00:03:29,515 I don't want to stay, you know, in the space of feasible solution, because once 57 00:03:29,515 --> 00:03:33,857 again, I want to deal with both aspects. And so what you're trying to do is 58 00:03:33,857 --> 00:03:36,866 basically look at both aspects simultaneously, and you will consider 59 00:03:36,866 --> 00:03:40,090 both feasible and infeasible configuration. 60 00:03:40,090 --> 00:03:43,822 So you will be in a larger space, okay? So you will both consider feasible and 61 00:03:43,822 --> 00:03:46,600 infeasible solution. And we'll try at the same time to 62 00:03:46,600 --> 00:03:49,480 decrease, you know, to satis-, to minimize the objective function, but also 63 00:03:49,480 --> 00:03:53,020 to find feasible solution. And I will show you how we can do that. 64 00:03:53,020 --> 00:03:56,920 And in graph coloring, there is a beautiful way to do that, which is nice 65 00:03:56,920 --> 00:04:01,614 to, really nice to explain, okay? So let's start with looking at the 66 00:04:01,614 --> 00:04:05,188 optimization as feasibility, okay? So I told you we are obsessed with 67 00:04:05,188 --> 00:04:07,960 feasibility, every optimization problem, we want to take it and view it as a 68 00:04:07,960 --> 00:04:12,379 sequence of feasibility problem. How can we do that in graph coloring? 69 00:04:12,379 --> 00:04:15,488 You know, this is what we do. We start, we have a feasible sol, we have 70 00:04:15,488 --> 00:04:19,480 a feasible a feasible solution. We have a certain number of colors. 71 00:04:19,480 --> 00:04:23,390 So, you can take a Greedy Algorithm and just try to find a feasible solution. 72 00:04:23,390 --> 00:04:26,120 And let's say we have K color so that brought you a solution, okay? 73 00:04:26,120 --> 00:04:29,530 So, once we have this k color, we say okay, so the next problem should have at 74 00:04:29,530 --> 00:04:34,406 least you know, one fewer color, okay? So, we want a solution, let's say with 75 00:04:34,406 --> 00:04:36,890 k-1one color, okay? What do we do? 76 00:04:36,890 --> 00:04:40,400 Well, we take all the vertices which are, you know, let's say color with color K 77 00:04:40,400 --> 00:04:45,450 and we basically replace them with a color, which is, from one to k-1, okay? 78 00:04:45,450 --> 00:04:47,570 Now what do we have? The problem is infeasible. 79 00:04:47,570 --> 00:04:49,730 We have plenty of violations, right? Or, maybe not. 80 00:04:49,730 --> 00:04:53,010 But, we have, you know, most likely, we'll have violations. 81 00:04:53,010 --> 00:04:56,358 So what you do is, we say, okay, so now the goal is to find a feasible solution 82 00:04:56,358 --> 00:05:00,617 with this k-1 colors, okay? And then obviously once we find a 83 00:05:00,617 --> 00:05:04,958 solution to that okay, so we k-2, k-3 and so on and so forth. 84 00:05:04,958 --> 00:05:08,509 Until we cannot find a feasible solution to our problem in which case we know that 85 00:05:08,509 --> 00:05:13,253 we have an optimal solution except that here we'll be using local search. 86 00:05:13,253 --> 00:05:17,652 We'll have no guarantees, okay? So, the key question here is obviously, 87 00:05:17,652 --> 00:05:22,525 okay, this is easy to do but how do we find a feasible solution. 88 00:05:22,525 --> 00:05:26,185 Okay, when, you know, how do we, you know, find a feasible solution, let's 89 00:05:26,185 --> 00:05:30,045 say, with k-1 color. And the way you can do that is 90 00:05:30,045 --> 00:05:34,860 essentially what we did in the first two lectures on, on graph coloring, right? 91 00:05:34,860 --> 00:05:37,506 So you look at the problem, you look at the violations and you try to minimize 92 00:05:37,506 --> 00:05:41,370 these violation, okay? So we have seen how to do this, okay? 93 00:05:41,370 --> 00:05:44,350 So, we just do that, okay? And that's the first approach for solving 94 00:05:44,350 --> 00:05:47,232 optimization problems, okay? Very much like the way constraint 95 00:05:47,232 --> 00:05:50,588 programming solves optimization problems. So you view that as a sequence of 96 00:05:50,588 --> 00:05:53,674 feasibility problems. At every one of these steps, you try to 97 00:05:53,674 --> 00:05:57,130 minimize The number of violations and then you have a feasible solution with 98 00:05:57,130 --> 00:06:01,574 k-1, you do the same with k-2 and so on and so forth, okay? 99 00:06:01,574 --> 00:06:03,870 So, so that's one of the, that's the first approach. 100 00:06:03,870 --> 00:06:08,130 The other approach is to say, you know, I don't like feasibility problems. 101 00:06:08,130 --> 00:06:11,970 I'm always going to assume that I'm feasible, okay, and I'm focusing on the 102 00:06:11,970 --> 00:06:17,490 objective function only, okay? That's what I'm obsessed about, okay? 103 00:06:17,490 --> 00:06:19,458 So, what do we need in graph coloring, okay? 104 00:06:19,458 --> 00:06:22,318 So the objective function is going to be minimized in the number of colors, and 105 00:06:22,318 --> 00:06:24,782 you assume that all, all the, all the, all the, you know, all the, the 106 00:06:24,782 --> 00:06:29,580 configuration is basically satisfying all the constraints, okay? 107 00:06:29,580 --> 00:06:32,719 Now, how to guide the search, that's the problem right? 108 00:06:32,719 --> 00:06:36,634 So because essentially it's like in the magic square example, right? 109 00:06:36,634 --> 00:06:39,340 So now we have all these legal colorings, okay? 110 00:06:39,340 --> 00:06:42,838 And now we're going to change the color of one particular vertex, but how is that 111 00:06:42,838 --> 00:06:46,560 going to affect the number of colors that we have? 112 00:06:46,560 --> 00:06:49,870 Most likely, it will not do anything right? 113 00:06:49,870 --> 00:06:53,220 Because if you could remove that color in you know, in one step and get a solution, 114 00:06:53,220 --> 00:06:56,350 that would be kind of a very unlikely event. 115 00:06:56,350 --> 00:06:59,934 And now you probably have a lot of colors with k-1 and you will have to get rid of 116 00:06:59,934 --> 00:07:03,686 many of them. But changing one is not going to change 117 00:07:03,686 --> 00:07:06,585 the number of colors. So the numbers of colors is kind of a 118 00:07:06,585 --> 00:07:09,980 very close way at looking at the objective function. 119 00:07:09,980 --> 00:07:13,514 So what you have to do, is essentially change the way you think about the the 120 00:07:13,514 --> 00:07:18,872 problems and objective function, okay? And this is where introducing the concept 121 00:07:18,872 --> 00:07:23,387 of color classes is useful, okay? So essentially what I'm going to say is 122 00:07:23,387 --> 00:07:27,417 that color classes i, Ci is going to be the set of vertices, which is color, with 123 00:07:27,417 --> 00:07:31,998 color i, okay? So essentially Ci is all the vertices in 124 00:07:31,998 --> 00:07:35,170 my huge graph, which I color with color i. 125 00:07:35,170 --> 00:07:39,410 Okay, C2 is all the vertices color with two, okay. 126 00:07:39,410 --> 00:07:42,658 And now to drive the search, I'm not going to look at how many colors I'm 127 00:07:42,658 --> 00:07:45,293 using. I'm going to look at the proxy, an 128 00:07:45,293 --> 00:07:49,160 indirect way of trying to minimize the number of colors, okay? 129 00:07:49,160 --> 00:07:52,436 And the way to do this is to look at the color classes and try to have huge color 130 00:07:52,436 --> 00:07:55,842 classes, right? Because, you know, when you have very few 131 00:07:55,842 --> 00:07:58,850 colors, typically you have large color classes, okay? 132 00:07:58,850 --> 00:08:01,510 So, this is the optimization function that we are going to use. 133 00:08:01,510 --> 00:08:05,138 It's an indirect objective function. It doesn't directly minimize the number 134 00:08:05,138 --> 00:08:08,800 of colors. It's what instead, what it's trying to do 135 00:08:08,800 --> 00:08:14,030 is to minimize the square of the sizes of the color classes, okay? 136 00:08:14,030 --> 00:08:18,230 So, in a sense, what I'm saying, I want big classes, I want big classes, okay? 137 00:08:18,230 --> 00:08:21,814 And so, think of it, you know, if there is one class with one color, and another 138 00:08:21,814 --> 00:08:26,710 class with 10,000 ver, you know, cal, 10,000, one vertice, one vertex. 139 00:08:26,710 --> 00:08:29,996 And another class with 10,000 vertices, if you move one, you know, from the 140 00:08:29,996 --> 00:08:33,974 other, from the large class. You're going to have really big increase 141 00:08:33,974 --> 00:08:37,366 in the, in the object, in the, in this objective function, where you maximize 142 00:08:37,366 --> 00:08:42,710 the size of the classes, okay? So this is what we're going to do, okay? 143 00:08:42,710 --> 00:08:46,752 Now once you do that, okay? So one, one of the problems that you may 144 00:08:46,752 --> 00:08:50,976 have is that it may be actually very difficult to move from one legal coloring 145 00:08:50,976 --> 00:08:55,494 to another one. You may be really, really heavily 146 00:08:55,494 --> 00:08:59,778 constrained by the fact that you're working in the space of legal coloring, 147 00:08:59,778 --> 00:09:02,875 okay? So, in a sense, in many of these 148 00:09:02,875 --> 00:09:06,140 applications, okay? So, when, once you are trying to keep 149 00:09:06,140 --> 00:09:10,084 the, the constraints feasible. You have to think of a neighbor-route 150 00:09:10,084 --> 00:09:14,896 that allows you to actually explore legal colorings in a reasonable fashion. 151 00:09:14,896 --> 00:09:18,709 And, and move, you know to places, okay? And not being stuck in a popular 152 00:09:18,709 --> 00:09:22,735 configuration where there is no way to move because I would violate at least one 153 00:09:22,735 --> 00:09:27,039 constraint, okay? And this is an idea that you can actually 154 00:09:27,039 --> 00:09:31,240 use inside inside coloring, okay? So, it's a richer neighborhood which is 155 00:09:31,240 --> 00:09:34,285 exploiting the stretch coloring much better, okay? 156 00:09:34,285 --> 00:09:38,348 This is called Kemp Chain, okay? So let's look at two color classes here, 157 00:09:38,348 --> 00:09:42,640 you have the, you know Ci and Cj, okay? And, and, and, and look at one of the 158 00:09:42,640 --> 00:09:46,506 vertices here, v, okay? And assume that you want to change the 159 00:09:46,506 --> 00:09:50,978 color of v, you know, to blue, okay? It's red right now, it has to go to blue, 160 00:09:50,978 --> 00:09:53,650 okay? Now it's very diffiuclt to do that right 161 00:09:53,650 --> 00:09:57,573 now, right? Because essentially, essentially, what 162 00:09:57,573 --> 00:10:02,708 you see is that v is connected to these three vertices, which are already color 163 00:10:02,708 --> 00:10:06,531 blue, okay? And therefore, if you color v to blue, 164 00:10:06,531 --> 00:10:09,820 you will have three constraint violation, and you can't do that, right? 165 00:10:09,820 --> 00:10:13,200 So we are in the space of legal colorings, okay? 166 00:10:13,200 --> 00:10:16,206 So what are we going to do? Well, an idea would be to say, oh, what I 167 00:10:16,206 --> 00:10:20,610 can do is take this guy and move it to the other side. 168 00:10:20,610 --> 00:10:24,420 But then I take these 3 guys which are blue, and I color them red, okay? 169 00:10:24,420 --> 00:10:27,606 So these guys have no violations with, you know, no violations between 170 00:10:27,606 --> 00:10:31,260 themselves, so you move them together, okay? 171 00:10:31,260 --> 00:10:33,756 But then what is the problem? Okay, so this guy here, you know, is 172 00:10:33,756 --> 00:10:37,700 connected to another guy which is red. oh, if I move this guy to the other side 173 00:10:37,700 --> 00:10:41,570 I have to, to this guy, and move is to the blue side, okay? 174 00:10:41,570 --> 00:10:43,930 Oh, but this guy is also connected to this blue guy, so I have to move this 175 00:10:43,930 --> 00:10:47,960 blue guy on the other side and then move these red guy to the other side. 176 00:10:47,960 --> 00:10:51,252 And that's the idea of Kemp Chains. So, you look at these strongly, these 177 00:10:51,252 --> 00:10:54,684 connected components and you'd taken all of the components that are connected 178 00:10:54,684 --> 00:10:58,267 there and you move them. You move the red to the blues and the 179 00:10:58,267 --> 00:11:01,804 blues to the red altogether, okay? So, you basically select all of these 180 00:11:01,804 --> 00:11:04,980 connected guys, okay that you, that you see, okay? 181 00:11:04,980 --> 00:11:08,204 And this is basically the various componensts, the various vertices here 182 00:11:08,204 --> 00:11:11,164 that are connected. And you take the red one, you make them 183 00:11:11,164 --> 00:11:12,729 blue. You take the blue one, you make them red, 184 00:11:12,729 --> 00:11:14,810 okay? And you swap them, essentially. 185 00:11:14,810 --> 00:11:17,634 And that's what you get. And now, magically, I mean, not 186 00:11:17,634 --> 00:11:21,802 magically, by design, right? So what we have here is that all the 187 00:11:21,802 --> 00:11:25,790 vertices that are blue, you know, have no violation. 188 00:11:25,790 --> 00:11:28,780 All the vertices that are red have no violation. 189 00:11:28,780 --> 00:11:31,250 And obviously, you're still at the length between the red and the blue. 190 00:11:31,250 --> 00:11:34,080 These are basically the same length than, than before, okay? 191 00:11:34,080 --> 00:11:36,463 So this is a much richer neighborhood, right? 192 00:11:36,463 --> 00:11:39,637 So you take a vertex, okay? And you take a color class in which you 193 00:11:39,637 --> 00:11:43,277 want to move that vertex, and then you find its component and you swap these two 194 00:11:43,277 --> 00:11:48,144 sets of vertices, okay? Much richer neighborhood, but the beauty, 195 00:11:48,144 --> 00:11:52,500 the beauty here is that we are staying in the feasible space, okay? 196 00:11:52,500 --> 00:11:56,140 So all the colorings are always going to be legal, and therefore we can only focus 197 00:11:56,140 --> 00:12:00,092 on the objective function. The same way as I have shown you when I 198 00:12:00,092 --> 00:12:03,880 was just swapping the color of the [UNKNOWN] vertex, okay? 199 00:12:03,880 --> 00:12:08,350 So it's a much richer neighborhood, I can explore many more things. 200 00:12:08,350 --> 00:12:13,670 Okay so the neighborhood is much larger. And, therefore, in general the quality is 201 00:12:13,670 --> 00:12:16,372 going to better, okay? So we have to deal with the efficiency 202 00:12:16,372 --> 00:12:20,090 side, but in a sense the neighborhood by definition is going to be better. 203 00:12:20,090 --> 00:12:24,960 But you're still feasible, and this is, this may be very interesting, okay? 204 00:12:24,960 --> 00:12:27,660 So, so, so we have seen two approaches so far. 205 00:12:27,660 --> 00:12:30,732 The first one was looking up you know, the, the first one we were obsessed with 206 00:12:30,732 --> 00:12:33,625 feasibility. And we were trying to solve the sequence 207 00:12:33,625 --> 00:12:36,991 of feasibility problems. In the second one, we were obsessed with 208 00:12:36,991 --> 00:12:40,364 the objective function. And we always stayed feasible and tried 209 00:12:40,364 --> 00:12:44,662 to improve the objective functions, okay? The third approach is to say okay, so I'm 210 00:12:44,662 --> 00:12:47,395 not obsessed by anything. I'm going to look at feasible and 211 00:12:47,395 --> 00:12:50,240 infeasible coloring. I can do both feasible at one some, at 212 00:12:50,240 --> 00:12:54,870 some point in the search and sometime it's feasible as well, right? 213 00:12:54,870 --> 00:12:58,730 And so now the search will focus on two things at the same time. 214 00:12:58,730 --> 00:13:01,546 We will have to focus on decreasing the number of colors and also we'll have to 215 00:13:01,546 --> 00:13:05,202 focus on decreasing the violations on the constraints, you know? 216 00:13:05,202 --> 00:13:09,380 Trying to ensure feasibility and find a legal coloring, okay? 217 00:13:09,380 --> 00:13:12,429 So, how do I do that? Typically what I want is an objective 218 00:13:12,429 --> 00:13:16,566 function that balances two things, okay? So I want to have something which looks 219 00:13:16,566 --> 00:13:19,900 at the object, at the objective and weight it, okay? 220 00:13:19,900 --> 00:13:23,186 And I want to have something which look, at, the, the, the violations on the 221 00:13:23,186 --> 00:13:28,130 constraints and also you know, is associated with a particular weight. 222 00:13:28,130 --> 00:13:30,940 And what I minimize is the overall thing, okay? 223 00:13:30,940 --> 00:13:34,216 So in a sense, sometimes I'm favor the objective function and sometimes I'm 224 00:13:34,216 --> 00:13:38,275 favor, you know, the feasibility. And the objective function is going to 225 00:13:38,275 --> 00:13:42,073 basically drive me to something which is good in both sense, okay? 226 00:13:43,170 --> 00:13:45,630 So, what is the neighborhood that I'm going to, you know, be concerned with 227 00:13:45,630 --> 00:13:47,590 here? We're going to take a very, very simple 228 00:13:47,590 --> 00:13:49,821 neighborhood. This is only changing the color of a 229 00:13:49,821 --> 00:13:52,341 vertex, okay? And then I need to introduce another 230 00:13:52,341 --> 00:13:56,610 concept so that we can express the drawing objective function nicely. 231 00:13:56,610 --> 00:14:00,590 I'm going to talk about Bad edges, okay? And a Bad edge is simply a net between 232 00:14:00,590 --> 00:14:04,570 two vertices, okay? Which are color with the same color. 233 00:14:04,570 --> 00:14:09,351 So these two vertices are linked, okay? They have the same color, so the edge is, 234 00:14:09,351 --> 00:14:12,760 is called a bad edge, okay? So it's a violation, essentially, okay? 235 00:14:12,760 --> 00:14:16,718 And I'm going to denote Bi, okay? The set of bad edges, which are colored 236 00:14:16,718 --> 00:14:19,797 with color i, okay? So, I have two edge, so for having a bad 237 00:14:19,797 --> 00:14:23,260 edge, I need these two vertices to have the same color, okay? 238 00:14:23,260 --> 00:14:27,620 If you know, that edge is considered a bad edge of color i, okay? 239 00:14:27,620 --> 00:14:30,896 I look at all my graph, and I look at all the vertices which are connect to all, 240 00:14:30,896 --> 00:14:34,068 all you know, the vertex, the two vertices that are connected an edges, by 241 00:14:34,068 --> 00:14:37,537 an edge. And are colored by i, I that these are 242 00:14:37,537 --> 00:14:42,210 you know, basically violation. And Bi is a set of those edges, okay? 243 00:14:42,210 --> 00:14:45,398 So concept of bare edges, okay. And know essentially what I want to do is 244 00:14:45,398 --> 00:14:48,620 find a nice way of expressing this objective function, okay? 245 00:14:48,620 --> 00:14:51,040 Once again, neighborhood is changing one color, okay? 246 00:14:51,040 --> 00:14:53,340 Now I have to focus on the objective function. 247 00:14:53,340 --> 00:14:56,540 I'm going to use exactly the same thing as, that we have done in when we were in 248 00:14:56,540 --> 00:15:01,500 the feasible space. I'm going to try to maximize the square 249 00:15:01,500 --> 00:15:07,921 of the sizes of the color classes, okay? So that basically drive me towards, you 250 00:15:07,921 --> 00:15:12,324 know, coloring with very few colors. And then, I have to remove the violation, 251 00:15:12,324 --> 00:15:14,600 okay? And the violation can be very, expressed 252 00:15:14,600 --> 00:15:17,857 very simply, right? So, what I want to do is to minimize the 253 00:15:17,857 --> 00:15:21,452 sum of the bad edges, okay? So, the, the, the sum of the sizes of the 254 00:15:21,452 --> 00:15:25,080 bad, the, the, the set of bad edges. And that's what you see over there. 255 00:15:25,080 --> 00:15:28,356 So, what I have to do is, maximize this, minimize this, and then I can combine 256 00:15:28,356 --> 00:15:31,632 these 2, okay? So one of, and the way I'm going to do 257 00:15:31,632 --> 00:15:35,060 this is by using this objective function, okay? 258 00:15:35,060 --> 00:15:38,490 So, so it takes the two aspects that I've mentioned before, okay? 259 00:15:38,490 --> 00:15:41,794 So we are basically here, you know maximizing the sizes of the color 260 00:15:41,794 --> 00:15:44,914 classes. Nothing fancy there, okay? 261 00:15:44,914 --> 00:15:48,581 I'm, you know, since I'm minimizing, overall I'm minimizing okay? 262 00:15:48,581 --> 00:15:51,672 So maximizing this is basically a minus of this, okay? 263 00:15:51,672 --> 00:15:54,620 So that's easy. And then the other things that you see 264 00:15:54,620 --> 00:15:58,960 here, is essentially this is the part which is minimizing the violation, okay? 265 00:15:58,960 --> 00:16:02,681 And instead of simply the sum of the sizes of the bad edges the, the you know 266 00:16:02,681 --> 00:16:07,127 the set of bad edges. What I'm doing here is multiplying this 267 00:16:07,127 --> 00:16:11,219 by the size of the color classes of these edges and then multiply the whole thing 268 00:16:11,219 --> 00:16:14,733 by 2, okay? Now you may say this guy is completely 269 00:16:14,733 --> 00:16:17,670 crazy, okay? But essentially there is a good reason to 270 00:16:17,670 --> 00:16:21,177 do this, okay? So this objective function has a 271 00:16:21,177 --> 00:16:25,090 beautiful property, okay? So, and before I tell you what that 272 00:16:25,090 --> 00:16:27,911 property is, okay? So one of the things you have to think 273 00:16:27,911 --> 00:16:30,622 about is. When we are trying to minimize these two 274 00:16:30,622 --> 00:16:33,870 components, well to minimize these two components together, okay? 275 00:16:33,870 --> 00:16:37,420 So let's say the objective and then feasibility, okay? 276 00:16:37,420 --> 00:16:41,580 The local minima, have no guarantees whatsoever on how, what this objective 277 00:16:41,580 --> 00:16:45,907 function is going to be. And how the very, the two aspects are 278 00:16:45,907 --> 00:16:50,748 going to be combined together, right? So you have no guarantees that when you 279 00:16:50,748 --> 00:16:55,270 reach a local minima, okay? So you actually have a feasible solution. 280 00:16:55,270 --> 00:16:59,283 Okay, a feasible coloring, okay? So in a sense, you know, you have, you 281 00:16:59,283 --> 00:17:03,313 don't know at that point that, that this minima is giving you a solution to your 282 00:17:03,313 --> 00:17:08,005 problem, okay? So what this objective function here does 283 00:17:08,005 --> 00:17:13,265 for you is that it guarantees that local minima are going to be legal coloring. 284 00:17:13,265 --> 00:17:17,512 Wow, that's, that's amazing, right? So I just minimized this function using 285 00:17:17,512 --> 00:17:20,330 local search. I get to a local minima and because of 286 00:17:20,330 --> 00:17:23,543 the design of this function you are guaranteed that, that minima is going to 287 00:17:23,543 --> 00:17:28,099 be a low, a legal coloring, okay? And therefore you know, you can just run 288 00:17:28,099 --> 00:17:32,396 this thing, you know, find the local minima or find a bunch of local minima. 289 00:17:32,396 --> 00:17:35,987 And all of them will be legal coloring and you can take, you know, you can take 290 00:17:35,987 --> 00:17:39,387 one of them, okay, as your solution, okay? 291 00:17:39,387 --> 00:17:41,880 And why is this true? This is the proof, it is a very simple 292 00:17:41,880 --> 00:17:45,232 proof, okay? And the key idea of the proof is okay, so 293 00:17:45,232 --> 00:17:49,250 let's assume that I have a coloring, okay? 294 00:17:49,250 --> 00:17:53,015 you know in color class C1 to Ck, so I have K colors, okay? 295 00:17:53,015 --> 00:17:56,295 And I'm going to assume that I have a violation, okay? 296 00:17:56,295 --> 00:17:59,590 So that means that one of the Bi is not empty. 297 00:17:59,590 --> 00:18:03,383 Okay, so I have a bad edge somewhere. And let's assume that this is color i, 298 00:18:03,383 --> 00:18:06,274 okay? And what I'm basically going to show you 299 00:18:06,274 --> 00:18:11,160 is that this particular configuration, okay, is not a local minima. 300 00:18:11,160 --> 00:18:13,840 It cannot be a local minima because I can improve it. 301 00:18:13,840 --> 00:18:17,759 I can improve it by changing the value of a single vertex, okay? 302 00:18:17,759 --> 00:18:21,236 So, what I do, is that I'm going to add a new color, k+1, and then I'm going to 303 00:18:21,236 --> 00:18:25,926 select the bad edges in Bi. And I'm going to select a vertex in that 304 00:18:25,926 --> 00:18:29,345 particular, in that particular edge, okay? 305 00:18:29,345 --> 00:18:33,438 And I'm going to change the color of that vertex from i to k+1, okay? 306 00:18:33,438 --> 00:18:36,742 and I'm going to show you that the value of the object function is going to 307 00:18:36,742 --> 00:18:40,518 decrease, and therefore this cannot be a local minima because I do this local 308 00:18:40,518 --> 00:18:44,851 move. And I have a better solution, okay? 309 00:18:44,851 --> 00:18:49,206 So by definition therefore all the local minima are going to be legal colorings, 310 00:18:49,206 --> 00:18:53,130 okay? So how do we do that? 311 00:18:53,130 --> 00:18:55,860 Well, we look at the objective function, right and only thing that we have to do 312 00:18:55,860 --> 00:18:59,276 is to see how it varies, okay? And typically there are these two, you 313 00:18:59,276 --> 00:19:01,856 know there are these two parts of the objective function and we're going to 314 00:19:01,856 --> 00:19:05,670 analyze them separately, right? So how does it vary? 315 00:19:05,670 --> 00:19:10,390 Well, with the left term, okay? So if we go back, the left term here is 316 00:19:10,390 --> 00:19:18,130 basically the, the term dealing with, feasibilities, okay? 317 00:19:18,130 --> 00:19:20,970 So this, this term essentially varies in this particular way. 318 00:19:20,970 --> 00:19:25,810 So this is the value before the, the, the local move that I'm making right now. 319 00:19:25,810 --> 00:19:29,568 This is the value after, okay? So what I do there, is that I decrease 320 00:19:29,568 --> 00:19:35,090 the bad edges by one and I also decrease the size of the color classes i by one. 321 00:19:35,090 --> 00:19:39,692 Because I move the color to k+1, okay. And so therefore the number of bad edges 322 00:19:39,692 --> 00:19:44,345 for this, this is the number of bad edges that I will get, okay? 323 00:19:44,345 --> 00:19:47,481 Of course the new edge, you know the, the, the vertex that I selected will have 324 00:19:47,481 --> 00:19:51,690 no violation because it's a new color that nobody else is using okay? 325 00:19:51,690 --> 00:19:55,224 So I do some algebraic manipulation and you know that this thing is going to be 326 00:19:55,224 --> 00:20:00,432 you know, basically the, the decrease in this left term is going to be greater. 327 00:20:00,432 --> 00:20:04,310 Actually is going to be equal to two times the size of Ci, okay? 328 00:20:04,310 --> 00:20:07,208 So you know this, this is how the left term is basically varying, now you look 329 00:20:07,208 --> 00:20:10,386 at the right term. The right term is, is looking at 330 00:20:10,386 --> 00:20:14,290 basically the objective, the objective part, the size of the color classes, 331 00:20:14,290 --> 00:20:17,300 okay? Now it's, you know, in the formula, it's, 332 00:20:17,300 --> 00:20:20,256 it's, it's negated, right? So what we, what we have to study is how 333 00:20:20,256 --> 00:20:23,154 this, you know, right term increases because there's going to be a decrease in 334 00:20:23,154 --> 00:20:26,813 the objective function. an increase in the well, it's going to be 335 00:20:26,813 --> 00:20:30,420 an increase in the objective function. So what we do there, we take, you know 336 00:20:30,420 --> 00:20:34,700 the square of the, the class is i because that's the class which is decreasing. 337 00:20:34,700 --> 00:20:39,055 The new, the new configuration will have one fewer vertex there, but will have 338 00:20:39,055 --> 00:20:43,515 also one more color classes which has a value of 1. 339 00:20:43,515 --> 00:20:47,736 You know, you manipulate this and you get what two C you know size of Ci minus 2 340 00:20:47,736 --> 00:20:54,010 and that term actually is smaller than the term we saw over there by 2. 341 00:20:54,010 --> 00:20:57,667 So we know that the objective function in this particular case is going to decrease 342 00:20:57,667 --> 00:21:02,047 at least by 2 [SOUND], okay? So which basically means that if your 343 00:21:02,047 --> 00:21:06,469 coloring is not legal, I always have a way to decrease the objective function by 344 00:21:06,469 --> 00:21:10,387 2. And therefore this is not a local minima, 345 00:21:10,387 --> 00:21:13,545 okay? So the beautiful objective function that 346 00:21:13,545 --> 00:21:17,067 I've shown you is this beautiful property, okay? 347 00:21:17,067 --> 00:21:20,902 That you know, it will give you every kind of local minima will give you a 348 00:21:20,902 --> 00:21:25,072 local coloring. So, once you search terminate, you don't 349 00:21:25,072 --> 00:21:28,936 have to worry. You will have a solution to your problem, 350 00:21:28,936 --> 00:21:32,990 with hopefully a small number of colors, okay? 351 00:21:32,990 --> 00:21:35,867 So, essentially, let's try to summarize what we saw here. 352 00:21:35,867 --> 00:21:38,138 Is when you have an optimization problem, okay? 353 00:21:38,138 --> 00:21:41,402 Which combines the objective function in a set of constraints, there are 3 ways to 354 00:21:41,402 --> 00:21:44,963 look at it. Solving a sequence of feasibility 355 00:21:44,963 --> 00:21:49,050 problem, or focusing on the objective function and always staying in the 356 00:21:49,050 --> 00:21:53,593 feasible space. Or trying to basically balance the search 357 00:21:53,593 --> 00:21:57,660 in the feasible space and the infeasible space. 358 00:21:57,660 --> 00:22:01,546 And hopefully, you know, having some properties, or some techniques, that will 359 00:22:01,546 --> 00:22:06,009 guarantee that the local minima are going to be feasible solutions. 360 00:22:07,710 --> 00:22:11,406 So the rest of the lecture is now going to focus on some more complex 361 00:22:11,406 --> 00:22:16,408 neighborhoods and also on hard to escape local minima, okay? 362 00:22:16,408 --> 00:22:17,886 Thank you.