Unstable NetworkSimplex Algorithm

[Chassein]

Hey everyone, i was using the NetworkSimplex? algorithm from Lemon to solve min cost flow Problems. I encountered the following problem. I have two different objective functions (c_1 and c_2) for the same minimum cost flow Problem (same graph, same supply, same bounds). Let x_i be the solution that I obtain by calling the NetworkSimplex? with the objective function c_i. (i=1,2) My problem is that x_2 performs about 2% better under objective function c_1 as x_1 does! (c_1(x_2) < c_1(x_1)). Note that c_1 and c_2 are very similar and defined by double values. I cannot solve the problem by making c_1 and c_2 integral after scaling them. Is this 2% inaccuracy just a normal unavoidable effect or is there something I can do to get more accuracy? I'm using Version 1.3.1.

Best Regards Andre Chassein

[Alpar Juttner]

Replying to Chassein:

I cannot solve the problem by making c_1 and c_2 integral after scaling them.

What does this mean? Is it impossible to scale the costs so that they will become integer or it is impossible to solve them using the integer costs (e.g. because of integer overflow)?

[Peter Kovacs]

You can also try another min-cost flow algorithm provided by LEMON. CapacityScaling should be the most stable and accurate in case of non-integer costs. Moreover, please note that the other algorithms actually does not support non-integer data. (They may handle them correctly, but it is not guaranteed.) See the warnings in their API documentation: http://lemon.cs.elte.hu/pub/doc/1.3/a00269.html http://lemon.cs.elte.hu/pub/doc/1.3/a00067.html

However, CapacityScaling can be significantly slower than NetworkSimplex.

[Chassein]

Hey everyone, I found out what was going wrong. The Problem was that my instances were infeasible. I didn't check that because the simplex returned an objective value. So, sorry for the unnecessary ticket.

The ticket can be deleted.

Regards, André Chassein