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

[Alpar Juttner]

Hi,

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

In fact, scaling the cost or capacity values (i.e. multiplying them by a
constant) should not affect the running time of NetworkSimplex at all.

Regards,
Alpar

> 
> 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
> >
> 
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user