[Help-glpk] Re: glpk numerical instability in 4.1, not in 4.0

[Andrew Makhorin]

>the attached model file performs as expected with GLPK 4.0,
>however, with 4.1 it generates a numerical instability, and apparently
>fails in the integer optimization. The platform is RedHat with gcc
>(see attached diff file.)

Disabling the lp presolver (--nopresol) resolves the problem:

------------------------------------------------------------------------
Model has been successfully generated
gm_scal: max / min = 3.024e+10
gm_scal: max / min = 3.127e+03
lpx_adv_basis: size of triangular part = 258
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
    133:   objval =   2.323985976e+01   infeas =   8.929026694e-19 (0)
*   133:   objval =   2.323985976e+01   infeas =   5.367928324e-14 (0)
*   165:   objval =   2.055250491e+01   infeas =   1.673661210e-13 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
gm_scal: max / min = 3.024e+10
gm_scal: max / min = 3.127e+03
+   165: mip =     not found yet; lp =   2.055250491e+01 (1, 0)
+   222: mip =   1.897971666e+06; lp =   2.055250491e+01 (6, 9)
+   264: mip =   1.236432006e+06; lp =   2.055250491e+01 (7, 12)
+   300: mip =   6.870907745e+05; lp =   2.055250491e+01 (8, 15)
+   330: mip =   2.736694626e+05; lp =   2.055250491e+01 (7, 18)
+   334: mip =   2.131338246e+01; lp =   2.055250491e+01 (6, 21)
+   343: mip =   2.131338246e+01; lp =     tree is empty (0, 27)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.6M (608868 bytes)
------------------------------------------------------------------------

However, your model is badly scaled (max aij / min aij = 3e10); that's
what is the real cause of numerical instability, not the presolver.
(I am surprising that 4.0 is able to successfully solve your model.)

I believe that the geometric mean scaling (used by default) is not
appropriate for badly scaled mip models, and the equilibration scaling
would be much more appropriate. Unfortunately, you cannot change the
scaling method from the command line, so please replace line 46 in the
file source/glplpx3.c, routine lpx_reset_parms:

   lp->scale = 3;

by the following line:

   lp->scale = 1;

to use the equilibration scaling by default. (I will made this change
in the next version of the package.)

Andrew Makhorin