[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-glpk] report a bug in GLPK
From: |
Andrew Makhorin |
Subject: |
Re: [Bug-glpk] report a bug in GLPK |
Date: |
Sat, 04 May 2013 11:39:34 +0400 |
> 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