1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Network optimization / Min cost flow problem

  1. Sep 24, 2013 #1
    1. The problem statement, all variables and given/known data

    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

    3. 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
    Last edited: Sep 24, 2013
  2. jcsd
  3. Sep 24, 2013 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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: Sep 24, 2013
  4. Sep 24, 2013 #3
    If I replace all undirected arcs by two oppositely oriented ones, wouldnt those just cancel out in the constraints?
    Regarding the issue of distinguishing between transhipped and generated power, thats the part im most confused about.

    Also, i was wondering if I put a dummy node wouldnt 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
  5. Sep 24, 2013 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    " ... 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.
  6. Sep 24, 2013 #5
    "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 recieve 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 ?
  7. Sep 24, 2013 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I can't read your solution: it is too 'weak' in terms of contrast, brightness, etc., to show up legibly on my screen. Sorrry.
  8. Sep 25, 2013 #7
    Here it is again

  9. Sep 25, 2013 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
  10. Sep 25, 2013 #9
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted