[Lemon-user] About using non-interger magnitudes in algorithm NetworkSimplex

[Kovács Péter]

Hi,

According to our benchmark tests, the magnitudes of capacities and costs 
do not significantly affect the running time of NetworkSimplex.

Regards,
Peter


On 2013.03.14. 8:54, Jose Luis Marín Español wrote:
>
> Thank you very much for your explanation.
>
> I will then use scaling of values to some integer range.  Any idea as to
> how the range will affect the computation time?  That is, will the
> choice of a large range (in order to minimize "quantization" errors)
> result in much longer computation times?
>
> JL
>
>
> 2013/3/13 Kovács Péter <kpeter at inf.elte.hu <mailto:kpeter at inf.elte.hu>>
>
>     Hi,
>
>     Actually, NetworkSimplex could support non-integer magnitudes, but
>     it would require careful modifications to avoid potential issues
>     related to inexact computations. We did not implement this feature
>     yet, but the reasons are only technical, not theoretical.
>
>     On the other hand, CapacityScaling algorithm already supports
>     non-integer arc costs (although it is usually slower than
>     NetworkSimplex).
>
>
>      > Would there
>      > be any problem in "discretizing" the original problem using a large
>      > range of integer values?
>
>     You can do such a scaling before using the algorithm.
>
>     Best regars,
>     Peter
>