[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] numerical instability

**From**: |
Michael Hennebry |

**Subject**: |
Re: [Help-glpk] numerical instability |

**Date**: |
Mon, 11 Jul 2011 22:22:36 -0500 (CDT) |

**User-agent**: |
Alpine 1.00 (DEB 882 2007-12-20) |

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."