SciGuy
asked on
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).
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).
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)
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)
ASKER
Thanks GwynforWeb. Let me think about that for a bit to see if it helps what Im trying to do...
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.
here is a nice link
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo1
here is a nice link
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo1
ASKER
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)?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
It turns out that my variant of the problem is not easily done using graph algorithms. I got it figured out with LP. Thanks.
Thanks for the points. :-)
you may get more help, if you create a "pointer" thread, in the Math & Science Topic Area, linking to this question (https://www.experts-exchange.com/Math_Science/askQuestion.jsp).
Good luck,
Rob.