[Help-glpk] Re: Failure with a basic LP problem

[Andrew Makhorin]

I just tried another (primal) method for the phase I, which is based on
minimization of the sum infeasibilities. Even if it starts from a "stupid"
initial basis, where b, c, d are basic, it runs with no problems:

lpt_read_prob: reading LP data from `bug.txt'...
lpt_read_prob: 4 variables, 3 constraints
lpt_read_prob: 7 lines were read
lpx_simplex: original LP has 3 rows, 4 columns, 6 non-zeros
lpx_simplex: presolved LP has 3 rows, 4 columns, 6 non-zeros
gm_scal: max / min = 1.000e+00
gm_scal: max / min = 1.000e+00
lpx_adv_basis: size of triangular part = 3
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
      3:   objval =   6.919351684e+09   infeas =   0.000000000e+00 (0)
*     3:   objval =   6.919351684e+09   infeas =   0.000000000e+00 (0)
*     5:   objval =   0.000000000e+00   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1M (72700 bytes)

Moreover, I've managed to solve an LP instance reported a while ago by
Tony Huerlimann. glpk 4.0 is not able to find its feasible basis, most
probably due to the same defect. But with the new method there are no
problems (except numeric instability on some iterations):

load_mps: reading LP data from `essa.mps'...
load_mps: name `MPSXNAME'
load_mps: 6806 rows
load_mps: 22481 columns
load_mps: 89138 non-zeros
load_mps: 1 right-hand side vector(s)
load_mps: 0 range vector(s)
load_mps: 1 bound vector(s)
load_mps: 99087 cards were read
lpx_simplex: original LP has 6806 rows, 22481 columns, 89138 non-zeros
lpx_simplex: presolved LP has 4197 rows, 9140 columns, 31913 non-zeros
gm_scal: max / min = 1.366e+10
gm_scal: max / min = 9.486e+04
lpx_adv_basis: size of triangular part = 4177
      0:   objval =   2.856479524e+07   infeas =   1.000000000e+00 (14)
<...>
*  4135:   objval =   3.133905506e+06   infeas =   1.773543037e-10 (0)
OPTIMAL SOLUTION FOUND
Time used:   26.0 secs
Memory used: 14.2M (14879004 bytes)

Looks like the new method is much more robust. However, I need to test
it on a larger set of lp instances before including it in glpk.

- Andrew Makhorin