[Help-glpk] upgraded version of the glpk simplex solver

[Andrew Makhorin]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

The method of one artificial variable implemented in the routine
lpx_prim_art (glplpx6a.c) and used on the phase I in the glpk simplex
solver has a serious defect: for some lp instances it erroneously
reports that the problem has no primal feasible solution. This error
appears when the column of the artificial variable, which enters the
basis to make it primal feasible, has large constraint coefficients,
that leads to small reduced costs of non-basic variables and
premature termination of the search, i.e. to wrong conclusion that
the problem has no primal feasible solution.

I included in the package the routine lpx_prim_feas that implements
the method of implicit artifical variables (based on minimization of
the sum of infeasibilities), which is a bit slower but much more robust.
The routine lpx_prim_feas has the same functionality and now it is used
instead lpx_prim_art (the latter is kept for archeologists).

If you wish to upgrade the package right now, just replace the module
glplpx6a.c in glpk 4.0 by the new version (please see the attachment)
and then rebuild the package in a usual way. The md5sum is:

6d75f2059eb57dfb5da22e9a9ff03710 *glplpx6a.c.gz

- - Andrew Makhorin
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (MingW32)

iD8DBQE/OZOX0XvyMFmB6BgRAoLhAJ9YWX9464TykGddR70JOba8lrh2YACeN3dU
ysdwwnApdTUUTxBXXs5MyGI=
=V41x
-----END PGP SIGNATURE-----

glplpx6a.c.gz
Description: application/gzip-compressed