Re: [Bug-glpk] report a bug in GLPK

[Andrew Makhorin]

> Thank you for your kind reply.  I copy the values of c,G,h to a txt file.
> Does this work? I also copy the results computed by GLPK and CVOXPT
> original LP solver to the txt file in the attachment. Another thing is: in
> our project, we are generating thousands of LPs and only a few are
> problematic. Not all of the results are incorrect. Thank you again.

As I explained in my previous e-mail, the error happens because of tiny
constraint coefficient 6.17e-17 . To avoid the error you need either to
disable geometric mean scaling or, that is much better, not to include
tiny constraint coefficients in the constraint matrix. 

------

1. Your original instance in lp format (note that the lp actually solved
   is extremely badly scaled since max|aij|/min|aij| = 1.287e+08):

minimize
   cost: -x3

subject to
   r1: -7.07e-01 x1 +7.07e-01 x2 +1.00e+00 x3 <=  1.39e-01
   r2: -1.00e+00 x1 +0.00e+00 x2 +1.00e+00 x3 <= -2.00e+01
   r3:  6.17e-17 x1 +1.00e+00 x2 +1.00e+00 x3 <=  2.05e+01
   r4:  7.07e-01 x1 -7.07e-01 x2 +1.00e+00 x3 <=  1.44e-01

bounds
   x1 free
   x2 free
   x3 free

end

GLPSOL: GLPK LP/MIP Solver, v4.50
Parameter(s) specified in the command line:
 --lp a.lp --nopresol --log a.log
Reading problem data from `a.lp'...
4 rows, 3 columns, 11 non-zeros
13 lines were read
Scaling...
 A: min|aij| =  6.170e-17  max|aij| =  1.000e+00  ratio =  1.621e+16
GM: min|aij| =  8.815e-05  max|aij| =  1.134e+04  ratio =  1.287e+08
EQ: min|aij| =  7.812e-09  max|aij| =  1.000e+00  ratio =  1.280e+08
Constructing initial basis...
Size of triangular part = 4
GLPK Simplex Optimizer, v4.50
4 rows, 3 columns, 11 non-zeros
      0: obj =   0.000000000e+00  infeas =  1.725e-03 (0)
      1: obj =   0.000000000e+00  infeas =  1.708e-03 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.0 Mb (29461 bytes)

------

2. Your original instance solved with --noscale option

GLPSOL: GLPK LP/MIP Solver, v4.50
Parameter(s) specified in the command line:
 --lp a.lp --nopresol --noscale --log a1.log
Reading problem data from `a.lp'...
4 rows, 3 columns, 11 non-zeros
13 lines were read
Constructing initial basis...
Size of triangular part = 4
GLPK Simplex Optimizer, v4.50
4 rows, 3 columns, 11 non-zeros
      0: obj =   0.000000000e+00  infeas =  2.000e+01 (0)
*     1: obj =   2.000000000e+01  infeas =  0.000e+00 (0)
*     3: obj =  -1.415000000e-01  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.0 Mb (29461 bytes)

------

3. Your instance with tiny and zero constraint coefficients removed
   (note that now the lp is well scaled)

minimize
   cost: -x3

subject to
   r1: -7.07e-01 x1 +7.07e-01 x2 +1.00e+00 x3 <=  1.39e-01
   r2: -1.00e+00 x1              +1.00e+00 x3 <= -2.00e+01
   r3:              +1.00e+00 x2 +1.00e+00 x3 <=  2.05e+01
   r4:  7.07e-01 x1 -7.07e-01 x2 +1.00e+00 x3 <=  1.44e-01

bounds
   x1 free
   x2 free
   x3 free

end

GLPSOL: GLPK LP/MIP Solver, v4.50
Parameter(s) specified in the command line:
 --lp b.lp --nopresol --log b.log
Reading problem data from `b.lp'...
4 rows, 3 columns, 10 non-zeros
13 lines were read
Scaling...
 A: min|aij| =  7.070e-01  max|aij| =  1.000e+00  ratio =  1.414e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 4
GLPK Simplex Optimizer, v4.50
4 rows, 3 columns, 10 non-zeros
      0: obj =   0.000000000e+00  infeas =  2.000e+01 (0)
*     1: obj =   2.000000000e+01  infeas =  0.000e+00 (0)
*     3: obj =  -1.415000000e-01  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.0 Mb (29461 bytes)

------


Hope this helps.


Andrew Makhorin