Re: [Bug-glpk] glpk bug

[Andrew Makhorin]

On Fri, 2018-02-02 at 13:30 +0100, Balázs Sziklai wrote:
> Dear GLPK Team,
> 
> 
> I have an mip problem (see attachment) that can be solved in under a
> second with glpk 4.58 but loops with glpk 4.64. That is, the gap does
> not go below 0.3% no matter how much time I keep running the solver.
> Gurobi also finds the solution (the same one that glpk 4.58 obtains).
> I would be very grateful for any feedback!
> Sincerely,
> Balázs Sziklai

Thank you for your report.

On solving your instance I found nothing unusual except maybe the
solution time; see glpsol output below and solution file attached.

Usually the maximal independent set problem (which your instance is, I
guess) takes relatively lesser time for small graphs, because clique
cuts are very efficient for this problem class (see for example
glpk/examples/misp.mod). Probably glpsol takes relatively much time due
to a pathological combination of the objective coefficients--if I
perturb the coeffs in your instance by .0001 (e.g. 1234 is replaced with
1234.0001), the instance is solved immediately on the root level.

As to glpk 4.58, it was just a lucky chance.


Andrew Makhorin


GLPSOL: GLPK LP/MIP Solver, v4.64
Parameter(s) specified in the command line:
 --cuts --pcost --lp tsst2.lp --log log -o sol
Reading problem data from 'tsst2.lp'...
tsst2.lp:1102: warning: missing final end of line
32 rows, 448 columns, 896 non-zeros
448 integer variables, all of which are binary
1102 lines were read
GLPK Integer Optimizer, v4.64
32 rows, 448 columns, 896 non-zeros
448 integer variables, all of which are binary
Preprocessing...
32 rows, 448 columns, 896 non-zeros
448 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 32
Solving LP relaxation...
GLPK Simplex Optimizer, v4.64
32 rows, 448 columns, 896 non-zeros
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (448)
*    58: obj =   1.581500000e+03 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
Gomory's cuts enabled
MIR cuts enabled
Cover cuts enabled
Clique cuts enabled
Constructing conflict graph...
Conflict graph has 448 + 0 = 448 vertices
+    58: mip =     not found yet <=              +inf        (1; 0)
Solution found by heuristic: 1544
Cuts on level 0: gmi = 4; clq = 3;
Cuts on level 8: gmi = 4; clq = 3;
+   113: >>>>>   1.548000000e+03 <=   1.552000000e+03   0.3% (9; 0)
+  4142: mip =   1.548000000e+03 <=   1.552000000e+03   0.3% (164; 636)
+  8210: mip =   1.548000000e+03 <=   1.552000000e+03   0.3% (249; 1317)
[...]
+133578: mip =   1.548000000e+03 <=   1.552000000e+03   0.3% (744;
25212)
Time used: 180.0 secs.  Memory used: 3.6 Mb.
+137367: mip =   1.548000000e+03 <=   1.552000000e+03   0.3% (763;
25945)
+140782: mip =   1.548000000e+03 <=   1.550000000e+03   0.1% (578;
27355)
+144122: mip =   1.548000000e+03 <=   1.549000000e+03 < 0.1% (92; 30724)
+144646: mip =   1.548000000e+03 <=     tree is empty   0.0% (0; 31937)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   191.5 secs
Memory used: 3.7 Mb (3912501 bytes)
Writing MIP solution to 'sol'...

sol
Description: Text document