Re: [Bug-glpk] bug in simplex for small dimensions ?

[pincon]

Le 24/05/2012 16:27, Andrew Makhorin a écrit :
> The error occurs because of tiny (i.e. close to zero) constraint 
> coefficients (2.22e-16). By default, before calling the simplex 
> solver, glpsol scales the lp instance with the geometric mean scaling 
> method, in which case tiny constraint coefficients lead to badly 
> conditioned constraint matrix, that, in turn, leads to excessive 
> round-off errors and therefore wrong results. To make the computations 
> more stable you need to either disable automatic scaling and using the 
> lp presolver (--nopresol --noscale), or, that is much better, remove 
> tiny constraint coefficients from your lp instance replacing them with 
> exact zeros. 

  Thanks for the explanation. If I understand
 well this is a case where the default scaling
 (geom mean + equil scaling but skip if LP is well scaled)
 gives bad results. I was really surprised so I sent this
 bug report (as geometrically the problem appears
 very simple, and also  any couple of neighbouring constraints
 should gives a very well conditionned matrix).

 Btw  when I set the scaling to:

geometric mean scaling + round scale factors to power of 2
equilibration scaling
equilibration scaling + round scale factors to power of 2

 I get an accurate result.

 But not with:

  geom mean + equil scaling + round scale factors to power of 2

And as you said no scaling is good too here. So for this particular
constraint matrix, equilibration scaling seems less sensible to this
problem of a tiny value.

 Thanks for developing and improving glpk.
Bruno

PS : The tiny value comes from the fact that the problem was set
in an automatic way from a numerical code.