Re: [Bug-glpk] possible bug in 4.52

[Andrew Makhorin]

Thank you for your bug report.

> 
> then the model does not solve.  Sometimes, I receive the message 
> 
> Assertion failed: piv1 != 0.0
> 
> Error detected in file ..\src\glpspx02.c at line 3026
> 
> >Exit code: 3    Time: 444.488
> 
> Since the assertion failed, it may be due to a bug in GLPK.
> 
>  
> 
> More often, for the same problem, I receive 
> 
> Error: unable to factorize the basis matrix (1)
> 
> Sorry, basis recovery procedure not implemented yet
> 
> ios_driver: unable to solve current LP relaxation; glp_simplex
> returned 5
> 
> +1664019: mip =     not found yet >=  2.855670500e+003        (11689;
> 536)
> 
> glp_intopt: cannot solve current LP relaxation
> 

Most likely this error happens because of Gomory cuts; these tend to be
almost linearly dependent, and the simplex solver sometimes is unable to
detect this. Sorry, glpk is not perfect. Just do not use --gomory.

Please note that your model is hard at least to be solved to optimality.
Though I managed to find a feasible solution close to the optimum (see
below). The proxy heuristic also seems to be efficient. See also the
model output attached.


Andrew Makhorin


GLPSOL: GLPK LP/MIP Solver, v4.52
Parameter(s) specified in the command line:
 -m model.mod --mir --pcost --bestp --log model.log
Reading model section from model.mod...
Reading data section from model.mod...
116 lines were read
. . .
Model has been successfully generated
GLPK Integer Optimizer, v4.52
1890 rows, 2988 columns, 15506 non-zeros
2988 integer variables, all of which are binary
Preprocessing...
128 hidden packing inequaliti(es) were detected
8 hidden covering inequaliti(es) were detected
308 constraint coefficient(s) were reduced
746 rows, 2400 columns, 11114 non-zeros
2400 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  7.500e+02  ratio =  7.500e+02
GM: min|aij| =  8.629e-01  max|aij| =  1.159e+00  ratio =  1.343e+00
EQ: min|aij| =  7.580e-01  max|aij| =  1.000e+00  ratio =  1.319e+00
2N: min|aij| =  4.219e-01  max|aij| =  1.500e+00  ratio =  3.556e+00
Constructing initial basis...
Size of triangular part is 746
Solving LP relaxation...
GLPK Simplex Optimizer, v4.52
746 rows, 2400 columns, 11114 non-zeros
      0: obj =   2.855630500e+03  infeas =  1.709e-01 (0)
*   112: obj =   2.856081402e+03  infeas =  1.388e-17 (0)
*   128: obj =   2.855636333e+03  infeas =  3.712e-16 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
MIR cuts enabled
+   128: mip =     not found yet >=              -inf        (1; 0)
Cuts on level 0: mir = 1;
+   821: mip =     not found yet >=   2.855637167e+03        (18; 0)
. . .
+ 49803: mip =     not found yet >=   2.855637167e+03        (573; 88)
Cuts on level 354: mir = 32;
+ 50900: >>>>>   2.857540500e+03 >=   2.855637167e+03 < 0.1% (592; 112)
+ 55337: mip =   2.857540500e+03 >=   2.855637167e+03 < 0.1% (608; 130)
+ 58553: mip =   2.857540500e+03 >=   2.855637167e+03 < 0.1% (647; 136)


GLPSOL: GLPK LP/MIP Solver, v4.52
Parameter(s) specified in the command line:
 -m model.mod --proxy 600 --log model1.log
Reading model section from model.mod...
Reading data section from model.mod...
116 lines were read
. . .
Model has been successfully generated
GLPK Integer Optimizer, v4.52
1890 rows, 2988 columns, 15506 non-zeros
2988 integer variables, all of which are binary
Preprocessing...
128 hidden packing inequaliti(es) were detected
8 hidden covering inequaliti(es) were detected
308 constraint coefficient(s) were reduced
746 rows, 2400 columns, 11114 non-zeros
2400 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  7.500e+02  ratio =  7.500e+02
GM: min|aij| =  8.629e-01  max|aij| =  1.159e+00  ratio =  1.343e+00
EQ: min|aij| =  7.580e-01  max|aij| =  1.000e+00  ratio =  1.319e+00
2N: min|aij| =  4.219e-01  max|aij| =  1.500e+00  ratio =  3.556e+00
Constructing initial basis...
Size of triangular part is 746
Solving LP relaxation...
GLPK Simplex Optimizer, v4.52
746 rows, 2400 columns, 11114 non-zeros
      0: obj =   2.855630500e+03  infeas =  1.709e-01 (0)
*   112: obj =   2.856081402e+03  infeas =  1.388e-17 (0)
*   128: obj =   2.855636333e+03  infeas =  3.712e-16 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
+   128: mip =     not found yet >=              -inf        (1; 0)
Applying PROXY heuristic...
Proxy's time limit set to 600 seconds.
Proxy's relative improvement set to 1.00 %.
Searching for a feasbile solution...
>>>>> first solution = 2.862701e+03;
Time used: 418.8 secs.  Memory used: 8.1 Mb
Starting proximity search...
>>>>> it:   1:   mip = 2.857441e+03;   elapsed time 436.0 sec.s
Bound exceeded = 310.810005. Proxy heuristic terminated.
Time used: 436.2.  Memory used: 8.1 Mb
Solution found by heuristic: 2857.4405
+   128: mip =   2.857440500e+03 >=   2.855637167e+03 < 0.1% (2; 0)
Time used: 436.3 secs.  Memory used: 4.0 Mb.
+   924: mip =   2.857440500e+03 >=   2.855640500e+03 < 0.1% (28; 0)
+  3961: mip =   2.857440500e+03 >=   2.855640500e+03 < 0.1% (37; 0)
+  8381: mip =   2.857440500e+03 >=   2.855640500e+03 < 0.1% (37; 0)

model2.log.gz
Description: GNU Zip compressed data