Network optimization / Min cost flow problem

[Yo388]

Homework Statement

Consider a power grid consisting of electricity producers that are connected to consumption points on the grid. The consumption points are affiliated with regional retail power companies that then distribute the power to their end users. The undirected graph (attached) gives the structure of the network where nodes 1,2,and 3 are location of the power generation plants and nodes 4,5,7 and 9 are power consumption points. The cost of transmitting power over any edge is 13$ per megawatt hour and there is no capacity constraint on an edge. It is possible for power to traverse both orientations. Each power generator has a max generation capacity in megawatt hours and a cost per megawatt hour generated(attached table below).

Only have to formulate the problem of finding the minimum-cost power generation and distribution strategy over the network to satisfy all consumption points as a linear program


2. Relevant info

Network

Cost table

The Attempt at a Solution

Tried solving it but i have never done undirected graphs before so i have no clue on how to come up with constraints. Basically I don't know how to incorporate the undirected graph arcs as those arcs can go either way and also because there is more supply than demand(dummy demand node perhaps?).I tried to incorporate the cost of megawatt hours in the main function though it might not be right.

P.S. MIGHT be an engineering question

 

[Ray Vickson]

Homework Statement

Consider a power grid consisting of electricity producers that are connected to consumption points on the grid. The consumption points are affiliated with regional retail power companies that then distribute the power to their end users. The undirected graph (attached) gives the structure of the network where nodes 1,2,and 3 are location of the power generation plants and nodes 4,5,7 and 9 are power consumption points. The cost of transmitting power over any edge is 13$ per megawatt hour and there is no capacity constraint on an edge. It is possible for power to traverse both orientations. Each power generator has a max generation capacity in megawatt hours and a cost per megawatt hour generated(attached table below).

Only have to formulate the problem of finding the minimum-cost power generation and distribution strategy over the network to satisfy all consumption points as a linear program2. Relevant info
View attachment 62121 Network
View attachment 62125 Cost table

The Attempt at a Solution

Tried solving it but i have never done undirected graphs before so i have no clue on how to come up with constraints. Basically I don't know how to incorporate the undirected graph arcs as those arcs can go either way and also because there is more supply than demand(dummy demand node perhaps?).I tried to incorporate the cost of megawatt hours in the main function though it might not be right.

View attachment 62124P.S. MIGHT be an engineering question

The standard method is to replace each undirected arc by two oppositely-oriented directed arcs with identical capacities and unit costs. And YES, using a dummy demand node is the way to handle excess supply.

However, a much more serious issue is to distinguish between 'transshipped' power and 'generated' power. For example, at node 2 the power shipped from node 2 (but just passing through, having been generated at some other node) has a different cost from the power actually generated at node 2. So, for example, the power from 2 to 5 may be partly generated at 2 and partly transshipped through 2 from somewhere else, and these two parts have different underlying costs; both incur the 13 cent transmission cost, but the stuff generated at 2 must also include the generation cost. Can you see a way to deal with this?

 

[Yo388]

The standard method is to replace each undirected arc by two oppositely-oriented directed arcs with identical capacities and unit costs. And YES, using a dummy demand node is the way to handle excess supply.

However, a much more serious issue is to distinguish between 'transshipped' power and 'generated' power. For example, at node 2 the power shipped from node 2 (but just passing through, having been generated at some other node) has a different cost from the power actually generated at node 2. So, for example, the power from 2 to 5 may be partly generated at 2 and partly transshipped through 2 from somewhere else, and these two parts have different underlying costs; both incur the 13 cent transmission cost, but the stuff generated at 2 must also include the generation cost. Can you see a way to deal with this?

If I replace all undirected arcs by two oppositely oriented ones, wouldn't those just cancel out in the constraints?
Regarding the issue of distinguishing between transhipped and generated power, that's the part I am most confused about.

Also, i was wondering if I put a dummy node wouldn't that mean that the excess demand is also being prodcued and since this is a minimization problem, it will increase the cost. Maybe that has to do with where I put the dummy node

 

[Ray Vickson]

If I replace all undirected arcs by two oppositely oriented ones, wouldn't those just cancel out in the constraints?
Regarding the issue of distinguishing between transhipped and generated power, that's the part I am most confused about.

Also, i was wondering if I put a dummy node wouldn't that mean that the excess demand is also being prodcued and since this is a minimization problem, it will increase the cost. Maybe that has to do with where I put the dummy node

" ... wouldn't those just cancel out in the constraints?" Don't ask: just do it and see what happens! Remember, though, that for an undirected arc between i and j there are two different flow variables, x(i,j) and x(j,i), depending on which of the two directed arcs are finally chosen by the LP solver.

What part of the following is confusing you? In a simpler version of the problem, suppose I have just three nodes 1,2 and 3, with supply at 1, 2 and demand at 3. If I have x(1,2) = 1 and x(2,3)= 2, part of the shipment x(2,3) = 2 is the shipment x(1,2)= 1 that came from 1 and just passed through 2; we add to it by generating another 1 unit at node 2. We cannot just write the cost as c(2,3)*x(2,3), with c(2,3) including the generation cost at 2, because that would mean we are also paying for node-2 generating cost on the part that was not generated at node 2. Presumably, the latter cost was already included in c(1,2)*x(1,2), and we don't want to pay it again, not to mention the fact that the generating costs at 1 and 2 might be different. Of course, I have not said anything about how to deal with the problem---I have just told you what you need to be careful about.


Re: dummy nodes: have you really never seen them before, in any problem? The cost of shipping to a dummy node is the cost of NOT shipping something to any real nodes; typically, that cost is zero, because we don't need to pay for shipping nothing at all (at least in most problems).

Now it is up to you: struggle with the problem until you 'get it'. It is important to be able to do that if you plan, for example, to become an applied Operations Research specialist in a company.

 

[Yo388]

" ... wouldn't those just cancel out in the constraints?" Don't ask: just do it and see what happens! Remember, though, that for an undirected arc between i and j there are two different flow variables, x(i,j) and x(j,i), depending on which of the two directed arcs are finally chosen by the LP solver.

What part of the following is confusing you? In a simpler version of the problem, suppose I have just three nodes 1,2 and 3, with supply at 1, 2 and demand at 3. If I have x(1,2) = 1 and x(2,3)= 2, part of the shipment x(2,3) = 2 is the shipment x(1,2)= 1 that came from 1 and just passed through 2; we add to it by generating another 1 unit at node 2. We cannot just write the cost as c(2,3)*x(2,3), with c(2,3) including the generation cost at 2, because that would mean we are also paying for node-2 generating cost on the part that was not generated at node 2. Presumably, the latter cost was already included in c(1,2)*x(1,2), and we don't want to pay it again, not to mention the fact that the generating costs at 1 and 2 might be different. Of course, I have not said anything about how to deal with the problem---I have just told you what you need to be careful about.Re: dummy nodes: have you really never seen them before, in any problem? The cost of shipping to a dummy node is the cost of NOT shipping something to any real nodes; typically, that cost is zero, because we don't need to pay for shipping nothing at all (at least in most problems).

Now it is up to you: struggle with the problem until you 'get it'. It is important to be able to do that if you plan, for example, to become an applied Operations Research specialist in a company.

"struggled" with it a little bit and this is what i came up with.

I think my constraints are right now. For the transshipped problem, if for example i made 12000 hours at node 2 and sent 1000 to node 1, 5000 to node 6, 6000 to 3 , and 1000imaginary hours to the dummy node. If I need to calculate the actual hours generator # 2 actually generated and didnt receive from other generators , i think doing X21+X2dd+X23+X26-X12-Xdd2-X32-X62 should work and tell me how many hours i actually generated at # 2.

In terms of my objective function i think its probably correct but not 100% on that.

What do you think ?

 

[Ray Vickson]

"struggled" with it a little bit and this is what i came up with.

View attachment 62175

I think my constraints are right now. For the transshipped problem, if for example i made 12000 hours at node 2 and sent 1000 to node 1, 5000 to node 6, 6000 to 3 , and 1000imaginary hours to the dummy node. If I need to calculate the actual hours generator # 2 actually generated and didnt receive from other generators , i think doing X21+X2dd+X23+X26-X12-Xdd2-X32-X62 should work and tell me how many hours i actually generated at # 2.

In terms of my objective function i think its probably correct but not 100% on that.

What do you think ?

I can't read your solution: it is too 'weak' in terms of contrast, brightness, etc., to show up legibly on my screen. Sorrry.

 

[Yo388]

I can't read your solution: it is too 'weak' in terms of contrast, brightness, etc., to show up legibly on my screen. Sorrry.

Here it is again

 

[Ray Vickson]

Here it is again

View attachment 62177

Still almost unreadable (actually, worse than the original) but I can just barely make out some of it. You don't need two variables x_{3dd} and x_{dd3}, for example. The dummy demand node 'dd' takes the excess supply; stuff flows INTO it only, not out of it. However, you are getting closer to a correct formulation.

Also, you still have not successfully separated out the effects of different 'generation' modes on the final cost; somehow, you need to make a distinction between those parts of x(i,j) that are generated at i from those other parts of x(i,j) that were generated elsewhere and just transshipped through node i and destined for node j.

 

[Yo388]

Also, you still have not successfully separated out the effects of different 'generation' modes on the final cost; somehow, you need to make a distinction between those parts of x(i,j) that are generated at i from those other parts of x(i,j) that were generated elsewhere and just transshipped through node i and destined for node j.

I think this has to do something with the dummy node? Because when we put the dummy demand, technically all supply is being used up. But in actuality its not as the excess is going to the dummy. I think if i can figure out which generator is sending the excess to dummy, that's probably the generator that's not generating power to its full capacity?