Linear Programming software

Roginald · 2011-09-08 14:45:28

Can anyone suggest any software to me that can solve generalized flow networks (i.e. networks with gains)? If not, I already have Maple and LP_Solve, so if someone can explain how to encode one of these networks as a linear program that would be OK, too. I also have Jensen's network_solver.xla for Excel which claims to solve these types of networks, but I can't make any sense of its input/output formats. It seems to always return flow 0, so if anyone has experience with this that's another option. Thanks for any help.

bobbym · 2011-09-08 14:51:39

Hi Roginald;

It sounds like you have all the software anyone needs. Can you describe the problem?

Roginald · 2011-09-08 15:35:20

Well I'm not sure how to encode a generalized flow network as a linear program, which is necessary for Maple/LPSolve. As far as I know they don't have any visual solver (i.e. I can't draw the network and have it solve it). As for the Jensen solver, it looks simple, but it just doesn't seem to work and I suspect I'm misunderstanding the input format somehow, but I haven't been able to work it out and there's no documentation.

So ideally I'm looking for a visual solver or a specific generalized network solver. If no such program exists, I'd settle for a basic guide to expressing a generalized network in such a way that it can be solved as a linear program.

Let me know if you need anymore info.

bobbym · 2011-09-08 16:05:02

Hi Roginald;

Questions like how do I find the girl of my dreams or how can I run more balls or how can I get better at math are too general for me to handle.

In order for me to have a chance at helping I need a specific problem. Network flow may have a different meaning to us. Would not be the first time someone was using the wrong terminology to describe something they want. If you can only provide a skeleton problem then I will work to see if I can figure out a method to get maple to do more of them.

Here is what I know about the types of network flow problems. First one was Euler's Koningsberg bridge. They are all described and solved using graph theory. There are knapsack, pert, chinese postman, travelling salesman, maximum flow, minimum flow... Maple has efficient algorithms for them all.

The thing I am saying is though some of them like the knapsack can be solved by linear programming it may not be the best way for all of them.

Also, QSopt is a very nice program for integer, linear, nonlinear, mixed integer, quadratic programming problems. It holds the record for the bigggest TSP of over 38000 cities!

One more thing, graph theory is a whole field by itself. If you are trying to learn it that will take months. There is no quick way especially if you are teaching yourself. if you are trying to find software that you can understand then that will take almost as long. If you are just trying to solve a specific problem then post it.

Roginald · 2011-09-08 17:46:06

OK, I understand what you're asking now.

4 nodes, labelled 0-4

arcs (from, to, capacity, gain): (0,1,1,1), (0,2,1,1), (1,3,1,3), (2,3,1,1), (3,4,3,1)

Find the max. flow from source (node 0), to sink (node 4) and the actual network that produces this flow.

Expected answer: Max. flow of 3, network is the arcs (0,1,1,1), (1,3,1,3), (3,4,3,1).
Explanation: Flow of one from source to node 1, then flow of 1 from node 1 to node 3 arrives as flow of 3*1=3 because gain of 3 on that arc, then flow of 3 from node 3 to node 4.

This is a very simple example. If you can help with this I'm sure I'll be able to extrapolate the results to a more realistic case. Thanks.

bobbym · 2011-09-08 20:39:47

Hi;

First things, it is usual to see such data as an adjacency matrix or to draw the graph. To make sure I have the problem correct, I will construct it.

This is how I am interpreting you data.

Or, this one does not have the correct weights because it is for another problem but notice how the edges have 2 values assigned to them.

Either of these ring a bell for you?

Please go here to get some more info:

http://broadcast.oreilly.com/2009/04/ma … ithms.html

Roginald · 2011-09-08 22:23:57

Adjacency matrix:
0 1 2 3 4
0 [0 1 1 0 0]
1 [1 0 0 1 0]
2 [1 0 0 1 0]
3 [0 1 1 0 3]
4 [0 0 0 3 0]
Where the entries are the arc capacities (I've made the matrix symmetric but the flow only goes one way).

The diagram you have shown is a flow network, with which I am familiar. A flow network is a generalized flow network with all the gains equal to 1. In a generalized flow network each arc has a gain associated with it that means the amount of flow leaving a node that travels over an arc with gain does not necessarily equal the amount of flow received at the other end.

For example: An arc (x,y) with gain = g. A flow of, say, f, leaves x and travels along (x,y). The amount of flow received at y is g*f.

So the adjacency matrix above does not take gain factors into account. In the example I gave when describing the problem, the arc (3,4) (or (3,sink)) has a gain factor of 3. So three times as much flow arrives at the sink as leaves from 3.

I hope this helps.

bobbym · 2011-09-08 23:09:07

Hi Roginald;

Then we need a digraph if the flows are only one way.

Math Is Fun Forum

#1 2011-09-08 14:45:28

Linear Programming software

#2 2011-09-08 14:51:39

Re: Linear Programming software

#3 2011-09-08 15:35:20

Re: Linear Programming software

#4 2011-09-08 16:05:02

Re: Linear Programming software

#5 2011-09-08 17:46:06

Re: Linear Programming software

#6 2011-09-08 20:39:47

Re: Linear Programming software

#7 2011-09-08 22:23:57

Re: Linear Programming software

#8 2011-09-08 23:09:07

Re: Linear Programming software

Board footer