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

[Lobron, David]

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