numerical instability - infinite loop

[Ali Baharev]

Dear Andrew,

This seems to me the same issue we discussed:

http://www.mail-archive.com/bug-glpk@.../msg00374.html

Although i have removed the tiny coefficients as you proposed and i
have also switched to equilibration scaling, i still have a bunch of
problems where this issue remains and i get into an infinite loop.

For example the problem here:

http://reliablecomputing.eu/glpk/

was originally obtained on a Linux machine (but i am unable to
reproduce it in the same environment), however i can reproduce the
infinite loop in the Windows environment...

Even if you cannot reproduce the problem, please have a look at the
the problem instance given at the above link.

Please help me:

What else should i remove / fix to zero / do whatever is needed to
either resolve this issue or realize that i will get into an infinite
loop and abandon the procedure?

For example i see int the dump.txt file that there is a row bound
2.01e-17 and an other row with the bound 1.75e+03. Can it cause this
strange behaviour?

Is it possible to set a predefined limit on the number of switches
back to the primal simplex method (at least i would not get into an
infinite loop)? I think i can implement this but it is a rather ugly
"fix"...

A feature request: could you please implement a function to dump the
lp object in hexadecimal format?

It is supported by the ISO/IEC 9899:1999 standard (7.19.6.1 The
fprintf function and 7.19.6.2 The fscanf function; the a conversion
specifier), or

http://www.dinkumware.com/manuals/?manual=compleat&page=lib_prin.html

Now, it is totally random if i can reproduce the issue using the
decimal dump even in the same software and hardware environment. The
chances would be higher with a hexadecimal dump.

Many thanks in advance!

Ali


_______________________________________________
Bug-glpk mailing list
Bug-glpk@...
http://lists.gnu.org/mailman/listinfo/bug-glpk

[Ali Baharev]

Dear Andrew,

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?

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.

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

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

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.

Many thanks for your help,

Ali


_______________________________________________
Bug-glpk mailing list
Bug-glpk@...
http://lists.gnu.org/mailman/listinfo/bug-glpk

[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



_______________________________________________
Bug-glpk mailing list
Bug-glpk@...
http://lists.gnu.org/mailman/listinfo/bug-glpk