Re: [Bug-glpk] 4.39 fails to produde optimal solution

[Andrew Makhorin]

> http://www.nabble.com/file/p25181506/glpkin.txt glpkin.txt
> http://www.nabble.com/file/p25181506/glpkout.txt glpkout.txt 
> http://www.nabble.com/file/p25181506/lpsolvein.lp lpsolvein.lp 
> http://www.nabble.com/file/p25181506/lpsolveout.txt lpsolveout.txt 

> The input are output files of glpk are generated by C++API while the
> stand alone solver produces the same result.

> The optimal result is produced by lp_solve.

> Is it because I am using too large constants? But they are all within
> the range of double.

Thank you for your bug report.

In fact, glpsol reports suboptimal solution 4.295539884e+04 while the
optimal solution is 4.295372226e+04.

The error appears because the dual simplex cannot provide sufficient
accuracy due to large coefficients in constraints r_7, ..., r_12.
I scaled the coefficients and rhs's by 1e-6 (please see attachment),
in which case glpsol correctly solved the instance:

GLPSOL: GLPK LP/MIP Solver 4.40
Reading problem data from `glpkin1.lp'...
12 rows, 48 columns, 216 non-zeros
48 integer variables, all of which are binary
178 lines were read
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech:  0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 12 rows, 48 columns, 216 non-zeros
glp_intopt: 48 integer columns, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  5.040e+01  ratio =  5.040e+01
GM: min|aij| =  6.708e-01  max|aij| =  1.491e+00  ratio =  2.222e+00
EQ: min|aij| =  4.650e-01  max|aij| =  1.000e+00  ratio =  2.151e+00
2N: min|aij| =  2.500e-01  max|aij| =  1.509e+00  ratio =  6.037e+00
Constructing initial basis...
Size of triangular part = 12
Solving LP relaxation...
*     0: obj =   5.975086563e+04  infeas =  0.000e+00 (0)
*    23: obj =   4.295331243e+04  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+    23: mip =     not found yet >=              -inf        (1; 0)
+    32: >>>>>   4.296858793e+04 >=   4.295331243e+04 < 0.1% (7; 0)
+    38: >>>>>   4.296691135e+04 >=   4.295331243e+04 < 0.1% (9; 3)
+    43: >>>>>   4.295752251e+04 >=   4.295331243e+04 < 0.1% (10; 5)
+    44: >>>>>   4.295372226e+04 >=   4.295331243e+04 < 0.1% (7; 8)
+    47: mip =   4.295372226e+04 >=     tree is empty   0.0% (0; 27)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (113395 bytes)


Andrew Makhorin

glpkin1.lp
Description: Binary data