Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 811

# Network Flow Modelling with GLPK

Hi,

I have a GNU MathProg model that models a network flow problem.  However, due to various reasons, I want to model this problem 'natively' using GLPK's C API.  I don't know much about Linear Programming, so can someone give me pointers as to how to approach this?

I think that I have to represent my graph as a node-edge incidence matrix, but I dont know what else I need to do.  I dont think I need code, I just dont know how my MathProg model (which is very intuitive to me) translates to a Linear Programming problem (which I know nothing about).
0
SciGuy
• 4
• 3
1 Solution

Commented:
SciGuy,

you may get more help, if you create a "pointer" thread, in the Math & Science Topic Area, linking to this question (http://www.experts-exchange.com/Math_Science/askQuestion.jsp).

Good luck,
Rob.
0

Commented:
Network flow problems can  be solved as linear programming problems by makng the unkowns the flow  along the  arcs(pipe). The constraints are that the flow along an arc should not exceed the capicity of the arc and  that the sum of the flow into each node should be 0, (ie flow in = flow out) there is no non negativity constraint on the flows.. The function to maximise is the flow from the source node.

There are better ways of solving these problems than using linear programming (googling should cough up the standard algorithm which is just continually sending flow along paths with free capacity)
0

Author Commented:
Thanks GwynforWeb. Let me think about that for a bit to see if it helps what Im trying to do...
0

Commented:
the maximal flow algorithm is the way to solve these and is used to solve linear programming problems of this form not the other way around as it is very rapid.

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo1
0

Author Commented:
Yeah, I guess using a true graph algorithm would make more sense.  So can I use Max Flow to find Min Cost Circulation (this is my real problem)?
0

Commented:
it depends on the form of your Min Cost Circulation problem which is a very general term.  Often these can be solved by using the transportation method and some times you just have to bang it out using the simplex method.  I would need to see more details about the problem.
0

Author Commented:
It turns out that my variant of the problem is not easily done using graph algorithms.  I got it figured out with LP.  Thanks.
0

Commented:
Thanks for the points. :-)
0

## Featured Post

• 4
• 3
Tackle projects and never again get stuck behind a technical roadblock.