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]

Could you try solving the two versions of the problem with another min-cost flow algorithm provided by LEMON? I think CapacityScaling should be the most accurate in case of non-integer costs, but it can be significantly slower than NetworkSimplex. They have (almost) the same interface, so you can easily switch between them.

[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