[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: [Help-glpk] upgraded version of the glpk simplex solver
Date: Wed, 13 Aug 2003 05:33:01 +0400

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
Version: GnuPG v1.2.2 (MingW32)


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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]