COIN-OR::LEMON - Graph Library

Opened 5 years ago

Closed 5 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:


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

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.

Version 0, edited 5 years ago by Peter Kovacs (next)

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 5 years ago by Peter Kovacs

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