[Help-glpk] GLPK primal simplex never terminates but dual simplex solves it in seconds

[Pavel Klinov]

Hello all,

I have an LP model which seems to give troubles to GLPK's primal
simplex algorithm. Here's the terminal output:

Preprocessing...
1403 rows, 1884 columns, 2383489 non-zeros
Scaling...
 A: min|aij| = 1.000e-003  max|aij| = 1.000e+000  ratio = 1.000e+003
GM: min|aij| = 3.164e-002  max|aij| = 3.161e+001  ratio = 9.990e+002
EQ: min|aij| = 1.001e-003  max|aij| = 1.000e+000  ratio = 9.990e+002
Constructing initial basis...
Size of triangular part = 1403
*     0: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*   500: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  1000: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  1500: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  2000: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  2500: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  3000: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  3500: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  4000: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  4500: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*  5000: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
.... and so on

However, if I switch it to dual simplex then it cracks it in seconds:

Preprocessing...
1403 rows, 1884 columns, 2383489 non-zeros
Scaling...
 A: min|aij| = 1.000e-003  max|aij| = 1.000e+000  ratio = 1.000e+003
GM: min|aij| = 3.164e-002  max|aij| = 3.161e+001  ratio = 9.990e+002
EQ: min|aij| = 1.001e-003  max|aij| = 1.000e+000  ratio = 9.990e+002
Constructing initial basis...
Size of triangular part = 1403
      0:                          infeas = 4.780e+005 (0)
      1:                          infeas = -2.274e-013 (0)
|   500: obj =  1.000000000e+000  infeas = 2.045e-029 (0)
|   718: obj =  1.000000000e+000  infeas = 8.318e-012 (0)
OPTIMAL SOLUTION FOUND
Time used:   4.4 secs
Memory used: 220.4 Mb (231146952 bytes)


I suspect that the problem could be due to potential numerical
instability because I have some small variable bounds (~ 4.0 10^-8)
but it's not reported by simplex. Can there be another reason or I
should just do some manual scaling to prevent it?

Let me know if you want to see the model (it's >1M so I'm not
attaching it to this email).

Thanks,
Pavel


-- 
cheers,
--pavel
http://www.cs.man.ac.uk/~klinovp