help-glpk
[Top][All Lists]
Advanced

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

```

reply via email to

 [Prev in Thread] Current Thread [Next in Thread]