1 00:00:00,180 --> 00:00:07,440 This example is referring to a spanning three with degree constraint, so, um, as you might have seen 2 00:00:07,440 --> 00:00:16,260 in the example of expanding tree, um, we define some, um, virtual demand for each node and then 3 00:00:16,260 --> 00:00:20,850 try to find out how we can create a graph, which is a tree. 4 00:00:22,190 --> 00:00:25,730 A connected one, but without any kind of loop. 5 00:00:27,080 --> 00:00:34,520 So, um, now we want to find out more characteristics of the graph and for some additional constraints. 6 00:00:34,700 --> 00:00:43,310 So if you look at this graph, which is a tree, um, we can easily calculate the degree of each node. 7 00:00:43,430 --> 00:00:51,620 For example, um, the degree of Node six is one because it has only one edge connected to it. 8 00:00:52,070 --> 00:00:53,210 Uh, degree of No. 9 00:00:53,690 --> 00:00:55,460 One is two. 10 00:00:55,470 --> 00:01:03,470 It has two edges connected to this note and the degree of node nine is three and so on and so on. 11 00:01:03,540 --> 00:01:12,380 OK, so maybe in some cases we want to uh, limit the degree of, uh, each node. 12 00:01:13,040 --> 00:01:20,840 So in order to do so, um, we have to, um, limit the number of edges that can be connected to a graph 13 00:01:21,290 --> 00:01:26,180 to to each node so we can write down for each eye. 14 00:01:26,450 --> 00:01:32,420 We can write down such an equation or constrain UIC. 15 00:01:32,420 --> 00:01:38,660 Plus, um, you see I should be less than end degree and the summation should be done over all the C 16 00:01:38,660 --> 00:01:40,420 except I uh. 17 00:01:40,430 --> 00:01:47,560 So we add this constraint to the formulation and see the results. 18 00:01:47,560 --> 00:01:57,650 So you can see here, if I limit the degree of each node to for example, two, then the same connection, 19 00:01:57,890 --> 00:02:02,030 the same dots are connected to each other in a different way. 20 00:02:02,420 --> 00:02:06,800 So here you can see that the maximum degree is two. 21 00:02:06,830 --> 00:02:08,630 What how should I write it down? 22 00:02:09,050 --> 00:02:10,790 Um, let me show you the. 23 00:02:12,550 --> 00:02:13,680 And page code. 24 00:02:14,260 --> 00:02:23,830 OK, so, um, here you can see the Python code and initially I import every required package and then 25 00:02:23,830 --> 00:02:25,780 I define the required variable. 26 00:02:25,780 --> 00:02:31,050 So the variables are the same as the example, um, minimum spanning tree. 27 00:02:31,810 --> 00:02:39,100 And, um, but we have to add, uh, new parameter called maximum degree. 28 00:02:40,560 --> 00:02:46,880 So a max degree is apparently is immutable, Pouncer, you can specify a default value for a. 29 00:02:47,890 --> 00:02:48,430 Or not. 30 00:02:49,120 --> 00:02:58,920 And also, um, the variables are exactly the same, then I create some random locations for those dots. 31 00:02:59,310 --> 00:02:59,520 Hmm. 32 00:03:00,310 --> 00:03:04,030 And, um, calculate the distance between each pair of them. 33 00:03:04,710 --> 00:03:05,170 OK. 34 00:03:06,300 --> 00:03:07,680 Then, um. 35 00:03:10,070 --> 00:03:17,960 There are some constraints for this model, and as we discussed before in the previous example, and 36 00:03:17,990 --> 00:03:22,360 each node, um, should follow the balanced rule. 37 00:03:22,410 --> 00:03:28,350 So how much we have generated is equal to how much we are consuming or exporting. 38 00:03:28,880 --> 00:03:37,490 So here only for node one, we have a production or generation, and at each node we have some amount 39 00:03:37,490 --> 00:03:39,020 of demand. 40 00:03:39,050 --> 00:03:41,030 Let's say I divide it by. 41 00:03:42,150 --> 00:03:47,610 And all of that in our region, especially something else or a constant number or whatever you want, 42 00:03:48,210 --> 00:03:55,320 and then how much exporting, how much importing from the other nodes do the summation and, uh, this 43 00:03:55,320 --> 00:03:57,830 constraint will create the balance at all. 44 00:03:58,290 --> 00:04:05,790 And then and the other constraint is telling us that if, um, no, it is connected to each other with 45 00:04:05,790 --> 00:04:11,190 two nodes are connected to each other, then a flow can exist between those two nodes. 46 00:04:11,760 --> 00:04:19,140 And these, um, and this one is, uh, telling us. 47 00:04:21,270 --> 00:04:24,420 The maximum degree of each note how should be specified. 48 00:04:24,480 --> 00:04:34,740 OK, so model UIC plus model, you see, I, um, summation oversee but for some specifics, not all 49 00:04:34,740 --> 00:04:41,640 the CS if I is different with C because we are not connected to each other, to ourselves and it should 50 00:04:41,640 --> 00:04:42,770 be less than one degree. 51 00:04:43,260 --> 00:04:47,280 And the objective function is as is the same as before. 52 00:04:47,280 --> 00:04:52,590 You multiply by the summation overall I can see. 53 00:04:52,830 --> 00:04:53,160 Mm hmm. 54 00:04:54,300 --> 00:04:58,960 Um, so here, let me give you a point here. 55 00:04:59,820 --> 00:05:01,890 So here you can see that. 56 00:05:01,890 --> 00:05:11,070 And in the if you write down this, uh, the code in this way, what will happen and it will put the 57 00:05:11,100 --> 00:05:16,970 RNC for every possible combination of RNC or in I and C J. 58 00:05:17,270 --> 00:05:18,840 OK, and. 59 00:05:20,500 --> 00:05:28,260 This way will also create some additional you when the RNC are also equal to each other. 60 00:05:28,540 --> 00:05:35,200 So to avoid that situation and I add an extra kind of, um. 61 00:05:36,820 --> 00:05:37,880 Specification. 62 00:05:37,930 --> 00:05:46,600 Yeah, so here, um, if R and C are, uh, exactly equal to each other, then. 63 00:05:50,530 --> 00:05:57,570 So if RNC are not equal to each other, then, um, the summation should take place. 64 00:05:57,970 --> 00:06:06,250 Otherwise it will create some situation that, um, you, um, are an R for example, you know, you 65 00:06:06,250 --> 00:06:07,760 want and want you to unter. 66 00:06:07,780 --> 00:06:11,330 So to avoid that we have to add this extra constraint. 67 00:06:11,350 --> 00:06:11,770 OK. 68 00:06:12,600 --> 00:06:16,260 Um, let's I should write off. 69 00:06:16,690 --> 00:06:24,840 OK, so, uh, this will create this will finish the definition of the constraints and we choose the 70 00:06:24,840 --> 00:06:30,360 solver as the GOP and we can specify the and and max degree. 71 00:06:30,390 --> 00:06:33,080 So let's, um, run the code with each other. 72 00:06:33,390 --> 00:06:35,390 So I run the first tab. 73 00:06:35,700 --> 00:06:36,160 OK. 74 00:06:36,180 --> 00:06:41,190 It is run successfully and also the second tab is done. 75 00:06:41,220 --> 00:06:41,980 OK. 76 00:06:42,480 --> 00:06:48,450 And the third type um is uh specify any equal to ten and max degrees for. 77 00:06:49,570 --> 00:07:00,070 So it takes time to finish to solve the statement, because, um, for example, if you have 10, um, 78 00:07:00,670 --> 00:07:07,480 nodes, then ten multiplied by nine is is telling you how many binary variables it will be. 79 00:07:07,480 --> 00:07:16,210 Nineteen, ninety and, uh, binary variables true to the power, 90 will be, uh, the number of combination 80 00:07:16,210 --> 00:07:16,960 that you might have. 81 00:07:17,290 --> 00:07:23,290 OK, so and finally I run this, you can get this graph you can see here. 82 00:07:26,230 --> 00:07:33,010 So initially, uh, as you can see here, the degree of the nose is the maximum degrees, three, for 83 00:07:33,010 --> 00:07:33,370 example. 84 00:07:33,370 --> 00:07:34,390 Here is three. 85 00:07:34,420 --> 00:07:35,350 Here is three. 86 00:07:35,980 --> 00:07:44,650 Uh, but if you add that constraint and consider that, then it means that, um, a new, uh, tree 87 00:07:44,650 --> 00:07:48,450 will be created and, uh, you can see it here. 88 00:07:48,460 --> 00:07:51,210 So I want the final time for you. 89 00:07:51,790 --> 00:07:52,810 You can do it as well. 90 00:07:53,590 --> 00:08:01,230 So, um, so this way it has to, uh, recalculate how they are. 91 00:08:01,300 --> 00:08:02,980 They should be connected to each other. 92 00:08:02,980 --> 00:08:11,320 So you can see here that this same location of the nodes, but different way of connecting them together. 93 00:08:11,940 --> 00:08:12,370 OK. 94 00:08:13,420 --> 00:08:14,200 Thank you very much.