Solved

Network Flow Modelling with GLPK

Posted on 2005-05-11
743 Views
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
Question by:SciGuy

LVL 25

Expert Comment

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

LVL 31

Expert Comment

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

LVL 1

Author Comment

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

LVL 31

Expert Comment

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

LVL 1

Author Comment

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

LVL 31

Accepted Solution

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

LVL 1

Author Comment

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

LVL 31

Expert Comment

Thanks for the points. :-)
0

Write Comment

Please enter a first name

Please enter a last name

We will never share this with anyone.

Featured Post

Suggested Solutions

Title # Comments Views Activity
withoutTen challenge 14 68
java continue statement 10 51
changePi Challenge 15 56
Path of Workbook 3 30
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
This article will show, step by step, how to integrate R code into a R Sweave document
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!