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
  • Last Modified:

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
Asked:
SciGuy
  • 4
  • 3
1 Solution
 
InteractiveMindCommented:
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
 
GwynforWebCommented:
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
 
SciGuyAuthor Commented:
Thanks GwynforWeb. Let me think about that for a bit to see if it helps what Im trying to do...
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
GwynforWebCommented:
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
0
 
SciGuyAuthor 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
 
GwynforWebCommented:
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
 
SciGuyAuthor 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
 
GwynforWebCommented:
Thanks for the points. :-)
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

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