Re: [Help-glpk] glpk 4.60 release information

[Andrew Makhorin]

Hi Chris,

> >         Some improvements were made in the primal and dual simplex
> >         solvers to make the solution process more numerically stable.
> 
> Indeed, the latest version is very stable: I tried several problems
> that had issues before without any problems. However, the perturbation
> code disables the check whether the objective limit has been reached,
> which results in a lot more iterations. In order to address this, I
> tried to keep track whether objective coefficients are modified and
> only disable the check in this case. I attach two patches that achieve
> this:
> -The fist one adds all potential coefficient changes away from the
> original, and subtracts only the ones that definitely restore the
> original coefficient. This is an upper bound to the number of modified
> coefficients and as such disables the check a few times more than
> strictly necessary.
> -The second patch (relative to the first one) works a bit harder to
> count the exact number of modified coefficients at every point.
> 
> A test case that nicely shows the improvement is with rmatr100-p5 from
> miplib (using a saved solution):
> glpsol --pcost rmatr100-p5.mps.gz --use rmatr100-p5.sol.gz
> 
> All cases finish the search with 3577 nodes, but the number of
> iterations needed are:
> original           960889 iterations
> first patch       480941 iterations
> second patch  468640 iterations
> 

Thank you for the patches.

Your technique should work, but it seems to me a bit complicated. 
I think that it is sufficient just to remove perturbation and repeat the
iteration like in other cases (iteration limit, time limit, etc.), i.e.
as follows:

   [...]
   /* check if the objective limit has been reached */
   if (csa->phase == 2 && csa->obj_lim != DBL_MAX
      && spx_eval_obj(lp, beta) >= csa->obj_lim)
   {  if (perturb)
      {  /* remove perturbation */
         perturb = 0;
         memcpy(csa->lp->c, csa->orig_c, (1+n) * sizeof(double));
         csa->phase = csa->d_st = 0;
      }
   [...]

Since perturbation of the objective coefficients is small (of order
1e-7), either no or a few iterations will be needed to restore dual
feasibility with a small change in the dual objective that will cause
the check to be signaled again once the simplex will switch to phase 2.

Should note that perturbing of objective coefficients implemented in
play_coef is equivalent to *relaxing* of (zero) bounds of dual
variables, so the perturbed objective is always better (*greater*) that
the original one at the same basic point.

Best regards,

Andrew Makhorin

PS: Please do not cc to the info-gnu mailing list.