Re: [Help-glpk] glpk 4.60 release information

[Chris Matrakidis]

Andrew,

>         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

Best Regards,

Chris Matrakidis

0001-keep-track-of-perturbed-coefficients-in-dual-simplex.patch
Description: Binary data

0002-keep-track-of-perturbed-coefficients-in-dual-simplex.patch
Description: Binary data