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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
