Network optimization / Min cost flow problem

In summary: 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...
  • #1
9
0

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
20130924_010606.jpg
Network
20130924_005655.jpg
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.

20130924_005605.jpg



P.S. MIGHT be an engineering question
 
Last edited:
Physics news on Phys.org
  • #2
Yo388 said:

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?
 
Last edited:
  • #3
Ray Vickson said:
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
 
  • #4
Yo388 said:
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.
 
  • #5
Ray Vickson said:
" ... 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.

20130924_232534.jpg


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 ?
 
  • #6
Yo388 said:
"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.
 
  • #7
Ray Vickson said:
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

page2.jpg
 
  • #8
Yo388 said:
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.
 
  • #9
Ray Vickson said:
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?
 

1. What is network optimization?

Network optimization is a mathematical technique used to find the most efficient way to allocate resources or distribute goods and services over a network. It involves minimizing costs or maximizing benefits while satisfying certain constraints.

2. What is a min cost flow problem?

A min cost flow problem is a type of network optimization problem where the goal is to find the minimum cost for transporting a certain amount of flow (e.g. goods, data, etc.) from a set of source nodes to a set of sink nodes. The cost of transporting flow through each edge is known, and the goal is to find the optimal flow distribution that minimizes the overall cost.

3. What are some real-world applications of network optimization?

Network optimization has a wide range of applications, including transportation and logistics planning, supply chain management, telecommunication network design, and energy distribution. It can also be used for optimizing traffic flow, scheduling tasks, and designing efficient computer networks.

4. What are some common algorithms used for solving network optimization problems?

Some commonly used algorithms for solving network optimization problems include the Shortest Path Algorithm, the Maximum Flow Algorithm, and the Minimum Cost Flow Algorithm. Other techniques such as linear programming, dynamic programming, and greedy algorithms can also be used depending on the specific problem.

5. What are the limitations of network optimization?

Network optimization is a powerful tool, but it also has its limitations. For instance, it assumes that the network structure is fixed and does not consider any changes or disruptions that may occur. It also relies on accurate data and may not be suitable for complex or highly dynamic systems. Additionally, the time and computational resources required to solve large-scale network optimization problems can be significant.

Suggested for: Network optimization / Min cost flow problem

Replies
13
Views
1K
Replies
9
Views
182
Replies
5
Views
407
Replies
27
Views
435
Replies
5
Views
305
Replies
12
Views
216
Replies
1
Views
1K
Back
Top