[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Bug-glpk] numerical instability (cycling?)

**From**: |
Andrew Makhorin |

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

**Date**: |
Tue, 25 Aug 2009 16:49:40 +0400 |

>* I am sure we both agree that getting into an infinite loop is not*
>* acceptable.*
>*> and applying geometric mean scaling makes the instance badly scaled.*
>* What is your opinion about the Curtis-Reid scaling algorithm?*
I do not think that another scaling algorithm would help. The defect
is in the simplex solver.
>*> However, a much better way is to replace tiny constraint coefficients*
>*> by exact zeros.*
>* 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).

**Re: [Bug-glpk] numerical instability (cycling?)**, *Andrew Makhorin*, `2009/08/22`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/22`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Andrew Makhorin*, `2009/08/25`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/25`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Andrew Makhorin*, `2009/08/25`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/25`
**Re: [Bug-glpk] numerical instability (cycling?)**,
*Andrew Makhorin* **<=**
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/25`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Andrew Makhorin*, `2009/08/28`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/28`
**Re: [Bug-glpk] numerical instability (cycling?)**, *Ali Baharev*, `2009/08/29`