[Lemon-user] Can the Cost type for CostScaling be floating point?

[Kovács Péter]

Hi David,

I'm glad to hear that you would like to use LEMON.

The CostScaling class in LEMON is indeed very similar to the original 
CS2 code, they have similar performance as well. However, the 
NetworkSimplex solution in LEMON is usually (much) faster, especially on 
relatively small networks (up to many thousands of nodes). So I suggest 
you to give it a try.

Anyway, all min-cost flow algorithms in LEMON have the same interface, 
so switching between them is trivial (see the attached example codes).

As for floating-point calculations, I agree with Alpár's notes. The 
min-cost flow algorithms in LEMON currently do not support 
floating-point data and they do not use the Tolerance class. So you 
should keep your scaling code (or try to replace it with a better one).

I attach code examples for using min-cost flow algorithms. The first one 
builds a simple network using API calls, while the other reads it from 
the example.dim file (DIMACS format).

Regards,
Péter




> Hi Alpar,
>
> Thank you very much for your reply, and for adding me to the list!  I'm excited to start using Lemon here at Akamai.
>
>>> Also, in a related question: is there any mincost algorithm that
>>> permits floating-point types for the demand type?
>>
>> A generic comment. Floating point calculations are always risky, due to
>> the inherent numeric errors. Lemon applies the concepts of Tolerance
>> classes to make the of the algorithms at least stable in case of using
>> floating point values while not causing running time penalties for
>> integer values.
>
> Very interesting!  Thank you for pointing this class out to me.  I like the design.
>
> Can Tolerance be used with cost scaling, or one of the other minimum-cost algorithms?  I don't see the Tolerance class used anywhere in that code, so my guess is not, but I wanted to check.
>
>> The the best and safest approach to avoid using floating point values
>> whenever it is possible. And it is possible in the vast majority of the
>> cases by applying an appropriate scaling of the input data.
>
> Yes, I totally agree.  In my case, floating point values were desired for the flow amount, capacity, and supply values (i.e., the "V" type in cost scaling) because our scaling code is very complicated and bug-prone.  We were hoping to simplify things by removing it.  But if integer stability is required, then we will keep our scaling.
>
> --David
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mcf_example.cpp
Type: text/x-c++src
Size: 1701 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20170525/8cd52e56/attachment-0002.cpp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mcf_example_dimacs.cpp
Type: text/x-c++src
Size: 1477 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20170525/8cd52e56/attachment-0003.cpp>
-------------- next part --------------
p min 12 21
n  1  20
n  2  -4
n  5   9
n  6  -6
n  9   3
n 10  -2
n 12 -20
a  1  2    0   11    70
a  1  3    0    3   150
a  1  4    0   15    80
a  2  8    0   12    80
a  3  5    0    5   140
a  4  6    0   10    60
a  4  7    0    2    80
a  4  8    0    3   110
a  5  7    0   14    60
a  5 11    0   12   120
a  6  3    0    3     0
a  6  9    0    4   140
a  6 10    0    8    90
a  7  1    0    5    30
a  8 12    0   16    60
a  9 12    0    6    50
a 10 12    0   13    70
a 10  2    0    7   100
a 10  7    0   10    60
a 11 10    0   14    20
a 12 11    0   10    30