Re: [Help-glpk] spx_simplex: numerical instability (primal simplex, phase I) and infinite looping in glpk on large model

[Andrew Makhorin]

> I am unsure why these models loop seemingly forever or what the
> messages from while they are running mean.

> Is there documentation on the meaning of the messages that appear
> while glpk is running? Are there any glpk methods or other
> approaches I can use to understand what is happening as glpk runs
> and catch errors sooner as it runs?

See the library reference included in the glpk distrobution,
specifically, description of the api routines lpx_simplex, lpx_integer,
and lpx_intopt.

> Here is another example of the mps file generated by the model when
> at a setting when it is in a infinite loop.

I tried running all your three models with glpsol. There is no
infinite loop. However, all your models are hard for the glpk b&b
solver, so it is unable to find the optimum in a resonable time.
Nevertheless, for less than 10 minutes glpsol managed to find
an integer feasible solution for your first model:

lpx_read_freemps: reading problem data from `test_mps.txt'...
lpx_read_freemps: problem EcoliOptTest
lpx_read_freemps: 10337 rows, 7896 columns, 38973 non-zeros
lpx_read_freemps: 1218 integer columns, all of which are binary
lpx_read_freemps: 75446 records were read
lpx_simplex: original LP has 10337 rows, 7896 columns, 38973 non-zeros
lpx_simplex: presolved LP has 6561 rows, 6702 columns, 30413 non-zeros
lpx_adv_basis: size of triangular part = 6544
      0:   objval =   1.000000000e+02   infeas =   1.000000000e+00 (7)
    200:   objval =   1.000000000e+02   infeas =   9.503194623e-01 (0)
...
* 10057:   objval =  -4.382417583e+00   infeas =   8.845162056e-13 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 10057: mip =     not found yet >=              -inf        (1; 0)
| 10800:   objval =  -4.382417583e+00   infeas =   4.450185637e+04 (0)
...
+ 48009: mip =   2.821065731e-11 >=  -4.382417583e+00        (29; 3)
...
TIME LIMIT EXCEEDED; SEARCH TERMINATED
Time used:   1223.0 secs
Memory used: 15.1M

Problem:    EcoliOptTest
Rows:       10337
Columns:    7896 (1218 integer, 1218 binary)
Non-zeros:  38973
Status:     INTEGER NON-OPTIMAL
Objective:  objective = 2.821065731e-11 (MINimum) -4.382417583 (LP)

Integer feasibility conditions:

INT.PE: max.abs.err. = 1.83e-11 on row 10335
        max.rel.err. = 1.83e-11 on row 10335
        High quality

INT.PB: max.abs.err. = 2.82e-11 on row 2656
        max.rel.err. = 2.82e-11 on row 2656
        High quality

End of output

Besides, your models are badly scaled. For example, many constraints
have too large coefficients at binary variables, for example:

R_EX_tsul_e__rcolpos: - 10000 R_EX_tsul_e__kcol + R_EX_tsul_e__var <= 0
R_EX_tsul_e__rcolneg: + 10000 R_EX_tsul_e__kcol + R_EX_tsul_e__var >= 0
EX_M_gln_L_b_rcolpos: - 10000 EX_M_gln_L_b_kcol + EX_M_gln_L_b_var <= 0
EX_M_gln_L_b_rcolneg: + 10000 EX_M_gln_L_b_kcol + EX_M_gln_L_b_var >= 0
EX_M_crn_b_rcolpos: - 10000 EX_M_crn_b_kcol + EX_M_crn_b_var <= 0
EX_M_crn_b_rcolneg: + 10000 EX_M_crn_b_kcol + EX_M_crn_b_var >= 0
EX_M_amp_b_rcolpos: - 10000 EX_M_amp_b_kcol + EX_M_amp_b_var <= 0
EX_M_amp_b_rcolneg: + 10000 EX_M_amp_b_kcol + EX_M_amp_b_var >= 0

I think this is the main reason of numerical instability, and this
explains wrong results on solving your second model:

Problem:
Rows:       10337
Columns:    7896 (1218 integer, 1218 binary)
Non-zeros:  38973
Status:     INTEGER OPTIMAL
Objective:  objective = -4.382417583 (MINimum) -4.382417583 (LP)

Integer feasibility conditions:

INT.PE: max.abs.err. = 8.57e-02 on row 8586
        max.rel.err. = 4.56e-02 on row 10260
        SOLUTION IS WRONG

INT.PB: max.abs.err. = 6.29e-13 on row 567
        max.rel.err. = 6.29e-13 on row 567
        High quality

End of output

(Although due to large constraint coefficients the resudual above
could be considered as relatively small.)

For some explanations of the second case see:
http://lists.gnu.org/archive/html/help-glpk/2007-04/msg00001.html

Andrew Makhorin