[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 15:33:11 +0400 |
Hi Ali,
> GCC supports the %la format specification.
> I made a decimal dump, 16 digits, and I can reproduce cycling on Win32
> and Linux, with different compilers.
I managed reproducing the cycling. In fact, it is a defect in glpk
simplex solver. However, your lp instance has tiny constraint
coefficients (see 'dump.lp'):
r_4: - 376.773086621089 x_8 + 8.88178419700125e-015 x_7
+ 1.00446428571434 x_5 + 49.1949765709737 x_4
+ 8.88178419700125e-015 x_3 + 570 x_2 - 771.540178571428 x_1 - ~r_4
= -963.113824335829
and applying geometric mean scaling makes the instance badly scaled.
I removed automatic scaling 'glp_scale_prob(lp, GLP_SF_AUTO);' at all,
and this allowed resolving the issue:
Writing problem data to `dump.lp'...
52 lines were written
0: obj = 0.000000000e+000 infeas = 1.514e+003 (1)
* 11: obj = 0.000000000e+000 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
* 11: obj = 4.176819207e-001 infeas = 0.000e+000 (0)
* 18: obj = -9.122774273e-001 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
* 18: obj = 5.965342043e-001 infeas = 0.000e+000 (0)
* 20: obj = -1.000000000e+000 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
* 20: obj = 1.487536843e-002 infeas = 0.000e+000 (0)
* 26: obj = -7.626125319e-001 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
* 26: obj = -8.950881698e-001 infeas = 0.000e+000 (0)
* 27: obj = -1.000000000e+000 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
* 27: obj = 3.029052923e-002 infeas = 0.000e+000 (0)
* 29: obj = -1.000000000e+000 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Never gets here!
However, a much better way is to replace tiny constraint coefficients
by exact zeros.
Andrew Makhorin
- 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 <=
- 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, 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