[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] spx_simplex: numerical instability (primal simplex, phas
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] spx_simplex: numerical instability (primal simplex, phase I) and infinite looping in glpk on large model |
Date: |
Fri, 13 Apr 2007 12:36:27 +0400 |
> 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