COIN-OR::LEMON - Graph Library

Opened 5 years ago

Closed 4 years ago

#509 closed defect (invalid)

Unstable NetworkSimplex Algorithm

Reported by: Chassein Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: release branch 1.3
Keywords: Cc:
Revision id:

Description

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

Change History (4)

comment:1 in reply to:  description Changed 5 years ago by 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)?

comment:2 Changed 5 years ago by 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.

Last edited 5 years ago by Peter Kovacs (previous) (diff)

comment:3 Changed 5 years ago by 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

comment:4 Changed 4 years ago by Peter Kovacs

Resolution: invalid
Status: newclosed
Note: See TracTickets for help on using tickets.