Re: [Help-glpk] Performance on l30

[Andrew Makhorin]

> l30 is one of the "problematic" (numerically difficult) problems on
> Mesazros' webpage:

> http://www.sztaki.hu/~meszaros/public_ftp/lptestset/problematic/

> Solving the other "problematic" problems on that page (excluding iprob)
> with glpsol (version 4.42), glpsol has no difficulties, which is a real
> feather in GLPK's cap.  However, glpsol failed on both in primal and
> dual mode on l30, no matter how many options to improve performance that
> I tried.

In fact, l30 is extremely degenerate in both primal and dual spaces;
besides it seems to be ill-conditioned near the optimum.

> I am guessing it has to do with extreme amounts of degeneracy, because
> if you add a tiny amount of random noise to the coefficients in the
> l30.mps file, producing say l30.perturbed.mps, glpsol can solve
> l30.perturbed in the dual mode (but not in the primal mode).  It might
> give a few "numerical instability" error messages, but it survives them
> to get to the answer, something it cannot do on the original l30 problem.

As a rule the steepest edge pricing along with Harris' ratio test used
in glpk simplex solvers by default are quite efficient against stalling,
so perturbation is not needed. However, in case of l30 these techniques
lead to numerical instability, most probably due to ill-conditioness.

> qsopt is an available revised-simplex binary for solving such problems.
>  qsopt also failed to solve l30 in the primal mode, but it then
> automatically switched to the dual mode in order to solve the problem.
> It did not need the perturbed problem to work.

This is used in the glpk b&b solver which automatically switches from
dual to primal in case of numerical instability. But in general case
it is unclear when to switch, because in most cases the instance can
be solved successfully by both primal and dual versions.

> Bixby, in one of this talks, mentioned that degeneracy was a problem in
> am early version of CPlex, which is why I decided to run the random
> noise experiment.  His comment was that adding random noise of size
> 1.e-5 was enough to cure the problem.

AFAIK in Cplex Bixby uses so called bound shifting as a remedy against
stalling. I think that many numerical difficulties could be avoided on
using a long-step version of the dual simplex; unfortunately it is still
not implemented in glpk.

> There are two features that would be welcome additions to GLPK: (1) a
> effective way of handling degeneracy so that, on l30 for example, you do
> not get a bunch of "numerical instability" messages followed by failure.
>  This ought to be possible with an additive random noise trick, or
> something similar, which only comes into play when it would otherwise be
> issuing the "numerical instability" message.  I am assuming from Bixby's
> comments that CPlex does do something like this.  (2) an automatic
> switch from solving the primal problem to solving the dual problem, as
> qsopt does, when the primal problem proves to be intractable.  If the
> primal phase I has exited, one already has a basis which one can use to
> get a head start on the dual problem.

Thank you for your suggestions.


Andrew Makhorin