[Lemon-user] Infinity loop problem with CycleCanceling

[Alpár Jüttner]

Hi Michael,


On Tue, 2011-01-04 at 11:13 +0100, meistermicha at gmx.de wrote:
> Hello,
> I am using the lemon library 1.2.1 to solve a minCostFlow-problem. I encountered a problem by using the cyclecanceling algorithm. Sometimes, depending on graph and flow settings, the function hangs in an infinity loop at cycle_canceling.h at line 935:
> 
> while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
> 
> I do not have deep insight into the algorithm but by debugging I saw
>  that mmc.cycleCost() returns constantly values around -10e-17.
>  Everything seems to work correctly by changing the line to
> 
> while (mmc.findCycleMean() && mmc.cycleCost() < -10e-10) {
> 
> Maybe this is a rounding issue?

Yes, it looks like that. The solution could be something like you
suggested. (LEMON provides a Tolerance concept to deal with this issue.)

The safest solution is however, to use integers instead of floating
point numbers. (You can do it in virtually any situation by scaling your
capacities and costs with an appropriately.)

Regards,
Alpar