Re: [Help-glpk] 4.48 vs 4.47

[Andrew Makhorin]

> I've wrote about this behaviour a while ago. Where GLPK 4.37 find a
> solution for a specific problem within ~4sec, newer version take
> longer. I just want to point out GLPK 4.51 is doing better! Still it's
> far from 3sec.

Thank you for your information.

Between 4.37 and 4.51 the glpk simplex solver was changed, in
particular, now the dual simplex solver requires the optimal solution to
be more numerically accurate. In your case optimal solution to lp
relaxation of the root subproblem found by the primal simplex is
re-optimized by the dual simplex to meet accuracy requirements, and this
takes a long time, because the optimal solution is highly dual
degenerate--most reduced costs of non-basic variables are close to zero.

You may reproduce the 4.37 behavior if you replace line 1316 in internal
routine ios_solve_node (file src/glpios01.c)

      parm.meth = GLP_DUALP;

with the following line

      if (!(tree->curr->level == 0 && tree->curr->solved == 0)) 
         parm.meth = GLP_DUALP;

In this case the node subproblem will be reoptimized for the first time
with the primal simplex that will take no iterations.

I'd like to note, however, that your mip instance is hard for glpk due
to its size and combinatorial structure. It is just a happy chance that
fpump is able to find the optimum.