[Help-glpk] Performance on l30

[ThumbTack]

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.

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.

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.

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.

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.