1 00:00:00,960 --> 00:00:09,360 This example is referring to the connected trees, so, um, we do have some random points on the surface, 2 00:00:09,700 --> 00:00:17,430 suppose here we have 10 points and what we want to do is try to find out the graph, which is a tree 3 00:00:17,880 --> 00:00:20,400 without any loop, which is a connected one. 4 00:00:20,790 --> 00:00:27,720 OK, so we want to find a connected graph which has no, um, loop inside it. 5 00:00:28,020 --> 00:00:28,480 OK. 6 00:00:28,710 --> 00:00:36,360 So in order to solve this problem, we need to find out a way that, um, first of all, we need to 7 00:00:36,360 --> 00:00:42,300 find a connected graph and then try to avoid having any kind of loop. 8 00:00:43,310 --> 00:00:51,560 OK, so in order to do so, we, um, we need to think about how we should do that, first of all, 9 00:00:51,740 --> 00:01:01,550 and in order to make the graph connected, uh, first of all, I put some, um, demand on each point, 10 00:01:01,940 --> 00:01:05,050 a virtual demand so it doesn't exist in reality. 11 00:01:05,600 --> 00:01:11,890 But we want to find out a way that, um, how can we supply all of these demands? 12 00:01:12,320 --> 00:01:19,220 So in order to do so, I assume that I have a generating unit at one of the point, just one of the 13 00:01:19,220 --> 00:01:27,200 points that say, point number one, you can you can put it everywhere else and then try to find a way 14 00:01:27,200 --> 00:01:33,720 that connect these, um, production point or generation point to the rest of the points. 15 00:01:33,800 --> 00:01:41,270 OK, and, uh, if you can formulate that, then it will be solved. 16 00:01:41,420 --> 00:01:51,350 OK, so, um, let's, uh, think about what kind of variables do we need in this, uh, formulation? 17 00:01:52,040 --> 00:01:52,520 OK. 18 00:02:41,610 --> 00:02:45,700 This example is referring to the problem of connected trees. 19 00:02:46,470 --> 00:02:50,270 Um, let me describe the problem for you. 20 00:02:50,460 --> 00:02:56,730 First of all, we do have a number of, uh, points scattered on a surface. 21 00:02:57,000 --> 00:03:01,080 Suppose we do have just 10 points in this example. 22 00:03:02,760 --> 00:03:05,340 And in order to solve the problem, um. 23 00:03:06,630 --> 00:03:09,940 We need to think about two different concerns. 24 00:03:09,960 --> 00:03:12,600 First of all, the graph should be connected. 25 00:03:13,520 --> 00:03:20,270 And it is a treat, the definition of the tree is that it's a connected graph without any loop. 26 00:03:20,840 --> 00:03:21,320 OK. 27 00:03:22,280 --> 00:03:22,970 So. 28 00:03:25,310 --> 00:03:28,370 How can we solve that problem? 29 00:03:29,500 --> 00:03:39,400 OK, and in order to solve that, I, uh, assume that, um, at every node there is a ritual demand 30 00:03:39,400 --> 00:03:41,440 that should be supplied. 31 00:03:41,980 --> 00:03:44,180 So every node has a demand. 32 00:03:44,580 --> 00:03:44,880 Hmm. 33 00:03:45,220 --> 00:03:47,730 No matter what the amount is. 34 00:03:47,740 --> 00:03:50,190 But we know that this demand should be supply. 35 00:03:50,500 --> 00:04:00,040 And in just one of those nodes, uh, I put the production plant and that production plant should be 36 00:04:00,040 --> 00:04:03,080 able to supply every demand in the system. 37 00:04:03,280 --> 00:04:10,520 So, um, this will give us the condition of connectivity. 38 00:04:11,110 --> 00:04:11,330 Hmm. 39 00:04:12,550 --> 00:04:17,530 In order to do so, let me think about what kind of variables do I need? 40 00:04:19,320 --> 00:04:23,490 First of all, which node should be connected to each other? 41 00:04:23,830 --> 00:04:24,240 Mm hmm. 42 00:04:24,930 --> 00:04:28,920 So then, um, definitely it will be a binary variable. 43 00:04:31,890 --> 00:04:40,080 Let's name it UIGEA, and the idea is the distance between Node I and J. 44 00:04:40,250 --> 00:04:46,880 OK, and for every node I have to write down the balance of supply and demand. 45 00:04:47,580 --> 00:04:53,100 So and every node, T minus L is equal to the outgoing flows. 46 00:04:53,730 --> 00:04:59,890 But keep in mind that only one of the nodes has GI or generation or production. 47 00:05:00,130 --> 00:05:04,710 OK, just node number one or any other nodes that you want for simplicity. 48 00:05:04,710 --> 00:05:06,990 I chose and number one. 49 00:05:07,530 --> 00:05:08,850 And also there is another. 50 00:05:10,440 --> 00:05:11,150 Condition. 51 00:05:14,110 --> 00:05:23,690 The flow only can exist, um, on, uh, on the lines that are that are connected to each other. 52 00:05:23,710 --> 00:05:25,530 For example, let me give you an example. 53 00:05:25,930 --> 00:05:35,800 For example, if one is connected to four, then UIGEA is one, then flow can get, uh, non-zero value. 54 00:05:36,010 --> 00:05:38,510 So the flows are assumed to be positive as well. 55 00:05:39,120 --> 00:05:46,030 OK, so if I solve that then the, uh, connected three can be found. 56 00:05:46,450 --> 00:05:49,870 So let me show you the Python code. 57 00:05:51,000 --> 00:06:02,160 So beginning, first of all, as usual, we have to import the required packages like plomo and matplotlib. 58 00:06:04,180 --> 00:06:06,250 Non-pay and also Dorando. 59 00:06:07,880 --> 00:06:15,920 And then I create a model, an abstract model model, and is the number of nodes for default value. 60 00:06:15,950 --> 00:06:19,570 I put eight and you can change it. 61 00:06:19,580 --> 00:06:21,160 I made it mutable. 62 00:06:21,170 --> 00:06:22,760 It means that you can update it. 63 00:06:23,270 --> 00:06:24,530 Uh, model I. 64 00:06:26,060 --> 00:06:27,500 Is the, um. 65 00:06:29,530 --> 00:06:38,980 Set representing the all the notes from one to end, and also Jay is the alias of AI model you is the 66 00:06:38,980 --> 00:06:43,360 variable is a binary one indicating I is connected to J. 67 00:06:44,580 --> 00:06:54,810 I, too, Jay Flow does the same, and I define it as a non-negative real G is the variable representing 68 00:06:54,810 --> 00:06:56,130 how much you are producing. 69 00:06:59,770 --> 00:07:08,020 I defined as just one variable, it's not needed to be defined or set because only one of the no's has, 70 00:07:08,040 --> 00:07:11,800 um, production or generation and the objective function at the end. 71 00:07:12,280 --> 00:07:13,510 And, uh, so. 72 00:07:14,610 --> 00:07:21,910 And maybe we need to initialize some, um, variables like X location and Y location. 73 00:07:22,670 --> 00:07:24,290 Um, these are not variables. 74 00:07:24,290 --> 00:07:30,960 These are parameters because we already know, um, where these points are allocated. 75 00:07:34,590 --> 00:07:41,790 In order to, um, uh, initialize the Poutre D, which is the distance between each pair of nodes we 76 00:07:41,790 --> 00:07:43,180 have to define as a perimeter. 77 00:07:43,230 --> 00:07:44,430 Here you can see. 78 00:07:45,780 --> 00:07:47,100 It's over a model I. 79 00:07:48,260 --> 00:07:54,250 Uh, it takes no negative real numbers and I initialize it using this rule. 80 00:07:54,270 --> 00:07:59,060 This rule is the famous rule security of X location. 81 00:07:59,490 --> 00:08:09,900 I want X location, J squared plus, um, my Y location or minus model Y location J square. 82 00:08:11,360 --> 00:08:17,110 And this will give the distance between each pair of nodes as well. 83 00:08:20,980 --> 00:08:27,340 And the balance equation, which is written on every eye, is defined using this rule. 84 00:08:27,820 --> 00:08:37,710 So for the first eye, we want to put only on the first eye and for the rest of them, there is no gee, 85 00:08:37,870 --> 00:08:38,670 yeah, OK. 86 00:08:38,860 --> 00:08:43,370 And here this quantity is the virtual demand at each point. 87 00:08:43,390 --> 00:08:48,070 So I just defined it as the I divide it by model and. 88 00:08:49,980 --> 00:08:52,920 So, um, on that's. 89 00:08:53,820 --> 00:08:56,180 What else is remaining, um. 90 00:08:58,510 --> 00:09:10,150 Um, rule number C two is the fact that if I if you is, um, non zero, then flow can get, uh, quantity. 91 00:09:11,210 --> 00:09:21,590 And also, um, uh, the objective function is multiplication of you are see by the RC for every hour 92 00:09:21,980 --> 00:09:23,310 I am seeing. 93 00:09:24,370 --> 00:09:25,110 OK. 94 00:09:25,200 --> 00:09:33,850 Uh, and also, what else is remaining, um, the objective function is model or f the sense is minimization 95 00:09:33,850 --> 00:09:40,900 solver is G.L. pick and model and um, let's assume there are ten points. 96 00:09:41,680 --> 00:09:48,700 I initialize the instance, solve the instance and print the objective function. 97 00:09:49,030 --> 00:09:52,360 And also first of all, I draw the points. 98 00:09:54,350 --> 00:10:02,300 Random generator points and also the show, the solid results I read on the program, and this one, 99 00:10:02,600 --> 00:10:09,260 since the points are randomly generated, each time you plot the graph, you might get a new one, but 100 00:10:09,260 --> 00:10:10,340 that should be fine. 101 00:10:11,910 --> 00:10:13,770 And the program is running. 102 00:10:16,710 --> 00:10:25,560 So you can see here that generation is on point one and it is trying to supply every note, so the notes 103 00:10:25,560 --> 00:10:30,460 are like this, but when you solve the problem, the connected tree is here. 104 00:10:30,540 --> 00:10:32,110 So why is it always tree? 105 00:10:32,140 --> 00:10:39,930 Because if you add any additional line, if you add any additional line, then an extra cost will be 106 00:10:39,930 --> 00:10:41,230 added to the objective function. 107 00:10:41,260 --> 00:10:44,390 So the program naturally will avoid that. 108 00:10:44,820 --> 00:10:48,450 It is not only connected, but it avoids any loop. 109 00:10:48,900 --> 00:10:49,710 Thank you very much.