1 00:00:00,060 --> 00:00:09,270 This example, we want to talk about the graph node coloring problem, so consider this graph, it has 2 00:00:09,270 --> 00:00:12,000 a number of nodes that are connected to each other. 3 00:00:12,690 --> 00:00:18,300 And from the graph, we just know how the nodes are connected to each other, that this is the input 4 00:00:18,300 --> 00:00:20,100 data of the problem. 5 00:00:20,130 --> 00:00:31,200 OK, so the question is, if we want to color the nodes in a way that no two adjacent nodes are painted 6 00:00:31,200 --> 00:00:34,660 with the same color, how many colors do we need? 7 00:00:34,680 --> 00:00:36,660 What is the minimum number of colors that we need? 8 00:00:37,020 --> 00:00:46,170 So suppose if we have nodes in or graph, then if we have any colors, we can easily solve this problem. 9 00:00:46,200 --> 00:00:51,100 OK, but there is a much smarter way to do this. 10 00:00:51,300 --> 00:01:01,110 For example, if you look at this graph, you can see by only two colors and the nodes are painted in 11 00:01:01,110 --> 00:01:05,250 a way that no two adjacent nodes are colored with the same color. 12 00:01:05,640 --> 00:01:11,910 So if you look at here, these two have different colors, but this yellow and this yellow one have 13 00:01:11,910 --> 00:01:14,910 the same color because they are not directly connected to each other. 14 00:01:14,940 --> 00:01:15,490 That's fine. 15 00:01:15,960 --> 00:01:20,800 So how can we formulated as a as an optimization problem? 16 00:01:20,820 --> 00:01:25,440 So first of all, we need the input data of the graph. 17 00:01:25,440 --> 00:01:37,230 So Elijah is one if I is connected to J and X, I see is telling us node eye is color with the color. 18 00:01:37,250 --> 00:01:44,970 See, so we have a set C it has a range of colors and I is the set of nodes. 19 00:01:45,390 --> 00:01:51,320 So we want to find out an optimal mapping between nodes and the colors. 20 00:01:51,570 --> 00:01:55,320 So we want to know which node should take which color. 21 00:01:55,620 --> 00:01:58,740 OK, so I see is a binary variable. 22 00:01:58,740 --> 00:02:00,600 X is the final variable. 23 00:02:00,600 --> 00:02:08,070 Iyengar aliased with each other so they are from the same sets nodes summation of these two variables 24 00:02:08,070 --> 00:02:10,170 multiplied by Elijah, less than one. 25 00:02:10,200 --> 00:02:13,760 So if Elijah is zero, it means that. 26 00:02:15,360 --> 00:02:21,090 To constraint, uh, can be easily satisfied because there is less than one automatically satisfied, 27 00:02:21,450 --> 00:02:28,850 it's inactive, and if energy is one, then Xixi plus SJC less than one. 28 00:02:28,890 --> 00:02:38,190 So that constraint is defined over the sets are and see for every injury and see if Alija is one, then 29 00:02:38,310 --> 00:02:40,070 the summation of these survival should be one. 30 00:02:40,230 --> 00:02:46,230 It means that if two nodes are connected to each other, they cannot get the same color. 31 00:02:46,680 --> 00:02:55,050 OK, and why is the objective function should be identical to see Xixi for every agency? 32 00:02:56,340 --> 00:03:07,020 And the last constraint is telling us that every node should take only one color so every node and every 33 00:03:07,020 --> 00:03:09,300 color can be assigned to only one node. 34 00:03:09,300 --> 00:03:13,950 OK, so let's have a look at the Python code for this purpose. 35 00:03:14,520 --> 00:03:16,200 So the Python code is here. 36 00:03:16,200 --> 00:03:22,130 I import, uh, required, um, packages. 37 00:03:23,130 --> 00:03:29,550 So first of all, uh, matplotlib networks for drawing the graph kind of, uh, plotts. 38 00:03:30,820 --> 00:03:40,390 And this is a built-In kind of facility in the networks package to plot the graphs that they're given 39 00:03:40,390 --> 00:03:45,100 sizes and also the position of these and those are determined. 40 00:03:45,460 --> 00:03:53,390 And then we'll import pion moments, possibly known by random and also Pande, OK? 41 00:03:53,440 --> 00:03:56,530 And then we construct the model. 42 00:03:57,610 --> 00:04:04,960 We assume that the model is an abstract one and is the number of nodes ie is the set of nodes is the 43 00:04:04,960 --> 00:04:07,270 same color as a set of colors. 44 00:04:07,990 --> 00:04:15,340 The maximum number of colors will be this number of nodes and L is a parameter showing that if I is 45 00:04:15,340 --> 00:04:22,360 connected to G to J, actually an X and Y are some variables. 46 00:04:22,360 --> 00:04:29,410 So X is a binary variable, but why is there no negative results. 47 00:04:29,410 --> 00:04:32,380 So, uh, we can easily solve that. 48 00:04:32,380 --> 00:04:38,500 And let's write down the, um, equation that we need. 49 00:04:38,500 --> 00:04:46,240 So you can see here that L multiplied by X I, C plus X Jaycee less than one. 50 00:04:46,690 --> 00:04:51,760 That constraint is the word I j and color and that's rules should be followed. 51 00:04:52,150 --> 00:04:58,660 And then the objective function should be bigger than a C multiplied by model and X. 52 00:04:58,660 --> 00:04:59,320 I see. 53 00:04:59,770 --> 00:05:03,880 And that's constraint is defined over I and C you can see here. 54 00:05:04,360 --> 00:05:11,380 And finally every node should take only one color that's here and the objective function is model that 55 00:05:11,380 --> 00:05:13,450 way and the sense is minimization. 56 00:05:13,480 --> 00:05:19,650 So we want to find out the minimum number of color required for, uh, paint in that graph. 57 00:05:19,960 --> 00:05:24,100 So since the model is linear, I choose the GOP. 58 00:05:24,100 --> 00:05:24,390 Okay. 59 00:05:24,520 --> 00:05:31,600 And solver and here we have already created the graph can see. 60 00:05:31,990 --> 00:05:37,840 And also here we we have access to the number of nodes in that graph. 61 00:05:38,200 --> 00:05:45,100 So model that N is initialized somehow and then the instance will be created here. 62 00:05:45,580 --> 00:05:49,830 OK, so let's run the code so far to see what's going on. 63 00:05:50,110 --> 00:05:57,510 So I run the whole tabs and I will explain the um results. 64 00:05:58,000 --> 00:06:01,670 So, um, let's begin from the first. 65 00:06:02,110 --> 00:06:07,120 So the first of the required pages are important, the second one as well. 66 00:06:07,120 --> 00:06:09,160 And the model is created here. 67 00:06:09,550 --> 00:06:18,610 And it is um, the instance will be constructed means that the L and other constraints are fed into 68 00:06:18,610 --> 00:06:19,050 the model. 69 00:06:19,420 --> 00:06:23,410 But keep in mind that I have not specified the L yet. 70 00:06:23,410 --> 00:06:26,130 So the connectivity matrix is not specified yet. 71 00:06:26,140 --> 00:06:28,300 So I have initialize that is equal to zero. 72 00:06:28,300 --> 00:06:30,190 So all of them are not connected to each other. 73 00:06:30,880 --> 00:06:42,010 But the model is right and we have to and update the L and feed the right connection matrix to the um 74 00:06:42,700 --> 00:06:43,550 instance. 75 00:06:43,570 --> 00:06:53,050 So for this purpose and what we do is we can easily find out which nodes are connected to which, so 76 00:06:53,050 --> 00:06:58,450 forth, and we create a for loop H in and G dot edges. 77 00:06:59,050 --> 00:07:09,430 If these two are connected to each other then um instance that Elijah is equal to one. 78 00:07:09,670 --> 00:07:17,590 OK, so from nodes and two nodes are uh found using these commands. 79 00:07:17,980 --> 00:07:28,630 OK, and then uh what we should do next is and let me double check it here for instance is updated at 80 00:07:28,630 --> 00:07:36,100 L l in the instance is updated and we have already defined as immutable parameter seed here. 81 00:07:36,100 --> 00:07:37,090 It's a mutual one. 82 00:07:37,240 --> 00:07:48,310 So it means that you can update their quantities and then and we can ask the more to solve it for us. 83 00:07:48,320 --> 00:07:50,470 So it is trying to solve the problem. 84 00:07:51,280 --> 00:07:57,550 Since it has some binary variables inside the model, it may take time to solve that. 85 00:07:58,420 --> 00:08:00,880 And, uh, so the model is solved. 86 00:08:03,160 --> 00:08:05,860 OK, you can see that, El. 87 00:08:07,010 --> 00:08:12,620 And it's printed here, for example, it's not really necessary to print all these, but for checking 88 00:08:12,620 --> 00:08:13,490 purpose, you can do it. 89 00:08:13,500 --> 00:08:17,270 So it means that one is connected to the volumes one and so on and so on. 90 00:08:17,690 --> 00:08:18,240 OK. 91 00:08:18,260 --> 00:08:30,080 And, um, finally, you can see here that, um, the graph is colored, OK, and each X I see has taken 92 00:08:30,080 --> 00:08:30,620 the value. 93 00:08:30,650 --> 00:08:33,590 So let me show you what's happening here. 94 00:08:33,800 --> 00:08:36,800 So here we have we can see easily. 95 00:08:36,800 --> 00:08:38,810 That's the what are the values of X? 96 00:08:38,810 --> 00:08:43,970 I see, for example, node one, color one is one. 97 00:08:43,970 --> 00:08:45,710 It means that no one is. 98 00:08:47,420 --> 00:08:50,270 Colored with color, No one, No. 99 00:08:50,270 --> 00:08:51,320 Two is colored with No. 100 00:08:51,320 --> 00:08:56,720 Two or three color, the number one, not four, is currently number two and so on and so on. 101 00:08:56,750 --> 00:09:02,690 OK, so and already we had a specified and each number means which color. 102 00:09:02,960 --> 00:09:12,770 OK, so, um, we should have a list for the columns and you can choose which color is selected. 103 00:09:13,070 --> 00:09:13,440 OK. 104 00:09:13,910 --> 00:09:14,750 And that's, it's.