Re: [Bug-glpk] numerical instability (cycling?)

[Andrew Makhorin]

>> I do not think that another scaling algorithm would help. The defect
>> is in the simplex solver.

> Could you please fix that? Would it be a lot of work?

It is not so easy. Currently, if some basic variables violate their
bounds due to excessive round-off errors, the primal simplex switches
to phase I to restore primal feasibility; and sometimes this may lead
again to the same (primal infeasible) basic solution.

>>> How can i figure out what "tiny" is?
>>
>> It depends on the instance's nature. I could suggest the following
>> criteria: a[i,j] is tiny if |a[i,j]| < 1e-8 * max|a[i,*]| assuming
>> that max|a[i,*]| is not very huge. For example, in the row:
>>
>> 1.23 x1 + 2.34 x2 + 3.45e-15 x3 + 4.56 x4 <= 5.67
>>
>> constraint coefficient '3.45e-15' is tiny and should be replaced by
>> exact zero (or skipped at all).

> This would be acceptable for me.

> Could you please suggest a criteria for "huge" in "max|a[i,*]| is not
> very huge".

> I have to automate this, because I generate thousand of LPs in an
> iteration loop.

Again, it depends on the instance's nature. I could suggest
scaling every constraint:

   sum a[i,j] * x[j] ~ b[i]

which has a[i,j] too small and large in magnitude, by scale factor
s = 1 / max|a[i,j]|:

   sum (s * a[i,j]) * x[j] ~ s * b[i]

and then replace a'[i,j] = s * a[i,j], for which |a'[i,j]| < 1e-7,
by exact zeros (or just remove them from the row list).