bug-glpk
[Top][All Lists]
Advanced

[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





reply via email to

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