Re: [Help-glpk] Small Integer Program takes long time to solve

[Andrew Makhorin]

> I have a small integer program whose optimal solution value is 49.
> Root relaxation is 48.5454. Since all the variables are integer, one
> expects it to stop when a solution with value 49 is found. Instead,
> GLPK takes a long time to converge.

> I also tried lp-solve, it found an optimal solution quickly (less
> than 0.1 second). Here is the output:

> Optimal solution                  49 after         72 iter,        34 nodes 
> (gap 0.0%).

> Value of objective function: 49
> Branch   Bound depth: 18
> Nodes processed: 34
> Simplex pivots: 72
> Number of equal solutions: 1

> I don #39;t think lp-solve is doing anything particular. It did not
> generate cuts and just branched on the first fractional integer
> variable.

> An mps file is attached. I would appreciate if someone can explain why
> it is taking so long.

Most probably lp_solve detects integrality of the objective that
helps it to finish the search once the gap becomes zero. A similar
feature was implemented in earlier versions of the glpk mip solver,
however, currently it is disabled due to some technical reasons.

I would like to note that your mip instance is hard, and there is
just a happy chance that the glpk solver (as well as lp_solve) finds
the optimum on the first try.