Re: [Help-glpk] numerical instability

[Michael Hennebry]

On Mon, 11 Jul 2011, Akhil langer wrote:

> @Robbie: The problem was very badly scaled (according to the definition
> given in the wiki). I used glp_scale_prob() but the warnings persist. In the
> program, the model gets modified with addition and deletion of rows between
> optimizations. Can I expect that GLPK will take care of rescaling required
> because of the changes in the model.

It's possible that some of yourLP's are inherently unstable.
In that case, scaling might not help enough, you will want more precision.
Ideally, you would move to a machine with more precision.
Another possibilty is to use another algorithm for solving linear equations.
This would involve editing GLPK.
IIRC, GLPK finds (B**-1)*x by maintaining B=LDU where L, D and U are
lower triangular, diagonal, and upper triangular matrices.
Often L and U are sparse if B is sparse.
LDU(B**-1)x = x is easily solved for (B**-1)x,
but since floating point is involved, the result is not exact.
To improve the accuracy, find p such that LDUp is approximately x
and find q such that LDUq is approximately the residual x-Bp.
The new improved answer is p+q.
It is useful to obtain Bp as accurately as possible.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."