1 00:00:00,380 --> 00:00:04,156 Well, I'm really happy to see you because if you made it that far, it basically 2 00:00:04,156 --> 00:00:07,932 means that you have successfully, you know, done the knapsack, you know, 3 00:00:07,932 --> 00:00:13,440 assignments and you are still willing to continue in the class. 4 00:00:13,440 --> 00:00:17,920 So, this is about coloring, and this is when things get more difficult. 5 00:00:17,920 --> 00:00:21,830 This is a very fantastic, amazingly beautiful assignment. 6 00:00:21,830 --> 00:00:24,406 You'll see that, okay. Conceptually, it's amazingly simple, 7 00:00:24,406 --> 00:00:26,076 right? So, we saw in the lecture, you have 8 00:00:26,076 --> 00:00:29,784 notes, you have edges between the notes. You want to color these things with as 9 00:00:29,784 --> 00:00:33,976 few colors as possible, okay. Such that two adjacent vertices are given 10 00:00:33,976 --> 00:00:37,980 a different color, okay. So, this is a beautiful graph. 11 00:00:37,980 --> 00:00:40,762 We've actually four nodes. It's a tree, so we could so optimal 12 00:00:40,762 --> 00:00:44,600 solutions very quickly, okay. And this is a particular solution. 13 00:00:44,600 --> 00:00:47,090 We've one node which is blue, another node red. 14 00:00:47,090 --> 00:00:50,626 Two green nodes, okay. And so we are using three colors, okay. 15 00:00:50,626 --> 00:00:52,960 So, this is what we will have to solve, okay. 16 00:00:52,960 --> 00:00:55,404 So this is the formalization of the problem, okay. 17 00:00:55,404 --> 00:00:58,420 You can look at it, okay. But, essentially the important things 18 00:00:58,420 --> 00:01:01,592 here is that we have a certain number of node and we have a certain number of 19 00:01:01,592 --> 00:01:05,168 edges, you know E. And that's what's going to drive the 20 00:01:05,168 --> 00:01:08,765 input of this assignment, okay. And we'll have a long, long, long list of 21 00:01:08,765 --> 00:01:12,233 edges because some of the problems we'll solve here are going to be pretty, pretty 22 00:01:12,233 --> 00:01:16,809 interesting in some societies, okay. So, we have a decision variable for 23 00:01:16,809 --> 00:01:20,500 everyone of the nodes and that's going to be the color of that node. 24 00:01:20,500 --> 00:01:22,670 That's going to be the output of this assignment, okay. 25 00:01:22,670 --> 00:01:25,886 So the assignment itself is basically minimizing the largest color that you are 26 00:01:25,886 --> 00:01:28,420 using. We are using numbers here, okay. 27 00:01:28,420 --> 00:01:33,900 So, you know, mini-, max, minimizing the maximum color that we are using, okay. 28 00:01:33,900 --> 00:01:36,602 And then we have only a single constraint which is reasonably easy. 29 00:01:36,602 --> 00:01:40,193 You know, two different, two adjacent vertices have to be given a different 30 00:01:40,193 --> 00:01:43,080 color, okay. So, when you look at this, you have to 31 00:01:43,080 --> 00:01:46,470 know what the input and the output are going to be, okay. 32 00:01:46,470 --> 00:01:49,535 So, the input here is going to have basically two ints, okay. 33 00:01:49,535 --> 00:01:53,423 The beginning that will tell you the size of the number of vertices, and then the 34 00:01:53,423 --> 00:01:58,150 number of edges, that's the two things that you will see there, okay. 35 00:01:58,150 --> 00:02:01,140 Number of vertices, number of number of edges. 36 00:02:01,140 --> 00:02:05,770 And then what you will have is a long list of edges, okay. 37 00:02:05,770 --> 00:02:09,910 Now an edge is basically defined by what? By essentially two vertices, okay. 38 00:02:09,910 --> 00:02:13,150 So, every line here that you see, the input is going to be basically telling 39 00:02:13,150 --> 00:02:16,498 you that there is an edge between, you know, the first vertex and the second 40 00:02:16,498 --> 00:02:20,122 vertex, okay. And, so that's basically going to be the 41 00:02:20,122 --> 00:02:22,062 input. So, the input is basically how many 42 00:02:22,062 --> 00:02:24,942 nodes, you know, how many, how many vertex, how many edges between these 43 00:02:24,942 --> 00:02:28,136 vertices. And then a long list of what these edges 44 00:02:28,136 --> 00:02:30,715 are. And that's just basically two, two 45 00:02:30,715 --> 00:02:33,569 vertices, okay. Now the output is going to be as usual, 46 00:02:33,569 --> 00:02:35,338 okay. So, what is the optimal solutions that 47 00:02:35,338 --> 00:02:37,245 you, or the best solutions that you have found? 48 00:02:37,245 --> 00:02:41,484 And whether it's optimal or not, okay. And then you will have also the colors of 49 00:02:41,484 --> 00:02:45,333 all these vertices, okay. So, for everyone of the vertex, you know, 50 00:02:45,333 --> 00:02:48,861 you will basically specify its color in the optimal well or the best form 51 00:02:48,861 --> 00:02:53,156 solution, okay. So, that's the basic idea, okay. 52 00:02:53,156 --> 00:02:58,262 This is a particular example, okay. So, you see that we have basically three 53 00:02:58,262 --> 00:03:02,700 vertices we have four vertices and three edges, okay. 54 00:03:02,700 --> 00:03:06,150 Those what you see there. And these are the various edges. 55 00:03:06,150 --> 00:03:11,420 We have an edge between node zero and node one, vertex zero, vertex one. 56 00:03:11,420 --> 00:03:14,940 We have another edge between vertex one and vertex two, and so on and so forth, 57 00:03:14,940 --> 00:03:18,605 that's what you see, okay. And then you see a particular of 58 00:03:18,605 --> 00:03:21,600 solutions there, which has basically three colors. 59 00:03:21,600 --> 00:03:25,285 And it's not proven optimal, and you see the various colors of these things 0122, 60 00:03:25,285 --> 00:03:28,880 okay. So, that's basically input. 61 00:03:28,880 --> 00:03:32,357 Very simple, long list essentially of edges and then the output, which is 62 00:03:32,357 --> 00:03:36,350 basically the color of every one of these vertices, okay. 63 00:03:36,350 --> 00:03:39,098 So, input output is very simple in this problem, okay. 64 00:03:39,098 --> 00:03:42,915 It's conceptually a very simple problem. But graph coloring is this beautiful 65 00:03:42,915 --> 00:03:46,770 property that is very very difficult to solve, okay. 66 00:03:46,770 --> 00:03:49,898 yeah, and this is an illustration of actually the two solution, the solutions 67 00:03:49,898 --> 00:03:54,440 that we just produce here. so let me give you some assignment tips 68 00:03:54,440 --> 00:03:57,600 here, okay. So, one other thing which is important 69 00:03:57,600 --> 00:04:02,310 whatever the, whatever the approach that you're actually using. 70 00:04:02,310 --> 00:04:06,350 Is that, you know, the degree of a node is important. 71 00:04:06,350 --> 00:04:09,202 The higher the degree of a node, you know, the more difficult it is, the more 72 00:04:09,202 --> 00:04:13,443 constrained that node is in a sense. You know, what the color that node can 73 00:04:13,443 --> 00:04:16,170 take is basically limited by all it's neighbors, okay. 74 00:04:16,170 --> 00:04:19,990 So, think about how that information can be exploited, okay. 75 00:04:19,990 --> 00:04:23,392 So, other things that you have to think about is that there are a lot and lot of 76 00:04:23,392 --> 00:04:27,646 symmetries in these problems, okay. So, we had a lot of lectures on 77 00:04:27,646 --> 00:04:31,230 symmetries inside the constrained programming lecture. 78 00:04:31,230 --> 00:04:35,902 Think about them, and think how they can be exploited inside this particular 79 00:04:35,902 --> 00:04:39,422 assignment, okay. So, what you see there is the solution 80 00:04:39,422 --> 00:04:41,590 there, okay. So, this is a solution, this is a 81 00:04:41,590 --> 00:04:44,600 solution which is completely symmetric, okay. 82 00:04:44,600 --> 00:04:47,300 You know, think about why these two things are symmetric. 83 00:04:47,300 --> 00:04:49,640 There is a very simple rule and, you know, this is essentially some of the 84 00:04:49,640 --> 00:04:52,331 techniques that we have seen in constrain programming there, for telling you what 85 00:04:52,331 --> 00:04:56,299 kind of symmetry this is. But, this can be exploited and if want or 86 00:04:56,299 --> 00:04:59,744 find actually, you know, very good solution and improve optimality, you will 87 00:04:59,744 --> 00:05:04,182 have to use things like this, okay. And then, there are other things that you 88 00:05:04,182 --> 00:05:06,719 want to do if, you know, if you want to improve optimality or if you want to 89 00:05:06,719 --> 00:05:10,340 find, you know, to get a, a sense of what your solution is. 90 00:05:10,340 --> 00:05:13,685 Try to find if they are easy lower bound that you can compute. 91 00:05:13,685 --> 00:05:17,249 There is one very simple conceptual lower bound that you can take, and that will 92 00:05:17,249 --> 00:05:20,780 tell you the best you can ever achieve, okay. 93 00:05:20,780 --> 00:05:23,704 So, you know, there are lot of structure here, although the problem is very simp-, 94 00:05:23,704 --> 00:05:26,499 you know it's very simple conceptually but there are lot of things that you can 95 00:05:26,499 --> 00:05:29,990 exploit and that's why I love this problem, okay. 96 00:05:29,990 --> 00:05:33,830 Now this is a beautiful graph here, you know, this is 250 vertices, it's about 97 00:05:33,830 --> 00:05:37,819 3000 edges, okay. Which basically means that the density 98 00:05:37,819 --> 00:05:41,264 here the den, you know, the density of the edges is 0.1% compared to the full 99 00:05:41,264 --> 00:05:45,410 graph, okay. It's a reasonably easy answer. 100 00:05:45,410 --> 00:05:48,340 I mean it's medium difficulty. It's still hard to prove optimality, but 101 00:05:48,340 --> 00:05:51,440 this is not some of the most difficult, this is not one of the most difficult 102 00:05:51,440 --> 00:05:55,184 instance. Now you can imagine a bushy, you know, it 103 00:05:55,184 --> 00:06:00,021 becomes when you have 50% density, okay. So, that's much more complex and much 104 00:06:00,021 --> 00:06:03,888 more difficult to solve, okay. So, so, this is essentially, you know, 105 00:06:03,888 --> 00:06:07,560 what I wanted to tell you about the graph coloring assignment. 106 00:06:07,560 --> 00:06:10,200 You can be really, really creative on this assignment. 107 00:06:10,200 --> 00:06:13,880 It's a fantastic assignment, okay. And I look forward to see you compete in 108 00:06:13,880 --> 00:06:16,930 finding a high-quality solution and proving optimality on some of these 109 00:06:16,930 --> 00:06:20,280 instances. Okay, have fun, it's going to be really 110 00:06:20,280 --> 00:06:21,440 interesting.