[Lemon-user] Infinity loop problem with CycleCanceling

[Kovács Péter]

Hi All,

> 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.)

Note that the current min cost flow implementations in LEMON support 
only integer capacities and costs. So this is a known limitation of 
these codes (not a bug), which can be found in their documentation as a 
warning.

In case of floating point costs, you can either scale them up (as Alpar 
suggested) or if the capacities and supply/demand values are integers, 
then you can also use the dual algorithm (CapacityScaling). This 
solution is stable for floating point costs.

Anyway, all min cost flow implementations should be improved to handle 
floating point values correctly. It is a long-standing issue, see e.g. 
the following ticket:
http://lemon.cs.elte.hu/trac/lemon/ticket/261

Regards,
Peter