[Lemon-user] Network Simplex with Floating Point Flows

[Samuel Gerber]

Thank you Péter,

I am using the network simplex for a multiscale optimal transport approach:
https://bitbucket.org/suppechasper/optimaltransport
http://jmlr.org/papers/v18/16-108.html

I used the approach you described (i.e. scaling the flows and cost to
integers) but that resulted in less accurate results than the floating
point approach in CPLEX.
Is it necessary to scale the costs as well or can those be integers? (I was
confused by the documentation which mentions that value type of the maps
must be convertible to each other).

I'd be happy to give an floating point implementation a go. I'd probably
need some more pointers to classes dealing with Tolerance's.

Cheers,
Sam



On Tue, Dec 5, 2017 at 5:29 AM, Péter Kovács <kpeter at inf.elte.hu> wrote:

> Hi Samuel,
>
> You're right, it wouldn't be too difficult to support floating-point input
> in the network simplex algorithm, but it hasn't been implemented yet.
>
> However, you can avoid floating-point values relatively easily by applying
> an appropriate scaling of the input data. Note that floating-point
> calculations are usually risky, due to the inherent numeric errors. So it
> may be safer to scale the data and use integers, although some algorithms
> in LEMON directly support floating-point data using the concepts of
> Tolerance classes (e.g. Preflow).
>
> If you would like to contribute, you are welcome to implement this
> improvement (in a similar way how other algorithms handle Tolerance
> classes).
>
> Regards,
> Péter
>
>
>
>
> On 2017-12-04 16:47, Samuel Gerber wrote:
>
>> Hi,
>>
>> I am curious what stands in the way of allowing floating point flows
>> (capacities, supplies, costs) in the network simplex algorithm?
>> Would this be difficult to add to the Lemon solver?
>> As far as I understand the CPLEX implementation works with floating point
>> inputs.
>>
>> Thank you
>> --
>> Samuel Gerber
>> R&D Engineer
>> Kitware, Inc.
>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>
>>


-- 
Samuel Gerber
R&D Engineer
Kitware, Inc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20171205/4e80d244/attachment.html>