[Lemon-user] problem with NetworkSimplex

[Alpár Jüttner]

> > What about the cost values? Are they integer-valued or not?
> > Note that the current implementations of minimum-cost flow algorithms 
> > in LEMON are intended to be used only with integer costs, while the 
> > number type can be double. (Actually, CapacityScaling is an exception, 
> > as it is stable for arbitrary real-valued arc costs, although this 
> > fact is only indicated in the latest development version yet.)
> Cost values are doubles...

This might be the culprit, indeed. While we do efforts to make the
algorithms working well with floating point values, it is impossible to
provide 100% safe solution to the problem of inexact calculation. Even
if an algorithm is stable on floating point input (i.e. it is guaranteed
not to get into an infinite loop), it is impossible to ensure that the
provided solution is "correct" (whatever it means in this contexts) in
general.

The safe solution is to use appropriately scaled integer values instead
floating point ones.

Regards,
Alpar