Re: [Bug-glpk] Re: numerical instability - infinite loop

[Andrew Makhorin]

Hi Ali,

> I just added a limit on the number of restarts in the simplex
> algorithm. In this way i do avoid the infinite loop. Could it be
> officially supported?

In principle, yes. However, there is a technical problem. The point
is that the numerical instability detected by the simplex solver,
as a rule, does not lead to cycling, and it would be difficult to
distinguish between cycling and non-cycling cases due to possible
degeneracy.

> It would be nice to have a function that makes a hexadecimal snapshot
> of the internal state of the solver and writes it to the disk so it
> can be reproduced.

Hexadecimal floats is a relatively new language feature, and I am
not sure that it is supported by all C/C++ compilers used to-day.
(Though this could be detected by configure script.)

> Could you please help me how my LP problems should be change to
> improve their numerical properties?

Then you should explain me your source problem and how you model it
with lp.

> I already removed the tiny coefficients as you proposed and i suspect
> now the tiny row bounds are causing the trouble.

Perhaps, yes, because row bounds are used as right-hand sides on
ftran and btran, and if the basis matrix is ill-conditioned, non-zero
rhs's may produce large round-off errors in the basic solution.

> An example is at the link i sent yesterday. The main.cpp takes the
> dump.txt as the input, builds the problem, writes it as dump.lp then
> starts the iteration and produces the log.txt console output. I can
> only reproduce this in the Windows environment.

I need a time to check your code.


Andrew Makhorin