This example is referring to the connected trees, so, um, we do have some random points on the surface,
suppose here we have 10 points and what we want to do is try to find out the graph, which is a tree
without any loop, which is a connected one.
OK, so we want to find a connected graph which has no, um, loop inside it.
OK.
So in order to solve this problem, we need to find out a way that, um, first of all, we need to
find a connected graph and then try to avoid having any kind of loop.
OK, so in order to do so, we, um, we need to think about how we should do that, first of all,
and in order to make the graph connected, uh, first of all, I put some, um, demand on each point,
a virtual demand so it doesn't exist in reality.
But we want to find out a way that, um, how can we supply all of these demands?
So in order to do so, I assume that I have a generating unit at one of the point, just one of the
points that say, point number one, you can you can put it everywhere else and then try to find a way
that connect these, um, production point or generation point to the rest of the points.
OK, and, uh, if you can formulate that, then it will be solved.
OK, so, um, let's, uh, think about what kind of variables do we need in this, uh, formulation?
OK.
This example is referring to the problem of connected trees.
Um, let me describe the problem for you.
First of all, we do have a number of, uh, points scattered on a surface.
Suppose we do have just 10 points in this example.
And in order to solve the problem, um.
We need to think about two different concerns.
First of all, the graph should be connected.
And it is a treat, the definition of the tree is that it's a connected graph without any loop.
OK.
So.
How can we solve that problem?
OK, and in order to solve that, I, uh, assume that, um, at every node there is a ritual demand
that should be supplied.
So every node has a demand.
Hmm.
No matter what the amount is.
But we know that this demand should be supply.
And in just one of those nodes, uh, I put the production plant and that production plant should be
able to supply every demand in the system.
So, um, this will give us the condition of connectivity.
Hmm.
In order to do so, let me think about what kind of variables do I need?
First of all, which node should be connected to each other?
Mm hmm.
So then, um, definitely it will be a binary variable.
Let's name it UIGEA, and the idea is the distance between Node I and J.
OK, and for every node I have to write down the balance of supply and demand.
So and every node, T minus L is equal to the outgoing flows.
But keep in mind that only one of the nodes has GI or generation or production.
OK, just node number one or any other nodes that you want for simplicity.
I chose and number one.
And also there is another.
Condition.
The flow only can exist, um, on, uh, on the lines that are that are connected to each other.
For example, let me give you an example.
For example, if one is connected to four, then UIGEA is one, then flow can get, uh, non-zero value.
So the flows are assumed to be positive as well.
OK, so if I solve that then the, uh, connected three can be found.
So let me show you the Python code.
So beginning, first of all, as usual, we have to import the required packages like plomo and matplotlib.
Non-pay and also Dorando.
And then I create a model, an abstract model model, and is the number of nodes for default value.
I put eight and you can change it.
I made it mutable.
It means that you can update it.
Uh, model I.
Is the, um.
Set representing the all the notes from one to end, and also Jay is the alias of AI model you is the
variable is a binary one indicating I is connected to J.
I, too, Jay Flow does the same, and I define it as a non-negative real G is the variable representing
how much you are producing.
I defined as just one variable, it's not needed to be defined or set because only one of the no's has,
um, production or generation and the objective function at the end.
And, uh, so.
And maybe we need to initialize some, um, variables like X location and Y location.
Um, these are not variables.
These are parameters because we already know, um, where these points are allocated.
In order to, um, uh, initialize the Poutre D, which is the distance between each pair of nodes we
have to define as a perimeter.
Here you can see.
It's over a model I.
Uh, it takes no negative real numbers and I initialize it using this rule.
This rule is the famous rule security of X location.
I want X location, J squared plus, um, my Y location or minus model Y location J square.
And this will give the distance between each pair of nodes as well.
And the balance equation, which is written on every eye, is defined using this rule.
So for the first eye, we want to put only on the first eye and for the rest of them, there is no gee,
yeah, OK.
And here this quantity is the virtual demand at each point.
So I just defined it as the I divide it by model and.
So, um, on that's.
What else is remaining, um.
Um, rule number C two is the fact that if I if you is, um, non zero, then flow can get, uh, quantity.
And also, um, uh, the objective function is multiplication of you are see by the RC for every hour
I am seeing.
OK.
Uh, and also, what else is remaining, um, the objective function is model or f the sense is minimization
solver is G.L. pick and model and um, let's assume there are ten points.
I initialize the instance, solve the instance and print the objective function.
And also first of all, I draw the points.
Random generator points and also the show, the solid results I read on the program, and this one,
since the points are randomly generated, each time you plot the graph, you might get a new one, but
that should be fine.
And the program is running.
So you can see here that generation is on point one and it is trying to supply every note, so the notes
are like this, but when you solve the problem, the connected tree is here.
So why is it always tree?
Because if you add any additional line, if you add any additional line, then an extra cost will be
added to the objective function.
So the program naturally will avoid that.
It is not only connected, but it avoids any loop.
Thank you very much.