Thanks, your explanation has been very helpful. I am trying to improve the form of my LPs and it seems to work in most cases.
Marcin On Tue, Jul 29, 2008 at 3:53 PM, Andrew Makhorin <[EMAIL PROTECTED]> wrote: >>> Probably this happens because your instance is not well conditioned, >>> so due to excessive round-off errors the presolved lp is unbounded >>> while the original lp is not. >> What does "not well conditioned" mean? What can I do about it? > > Ill-conditioning means, roughly speaking, that small changes in the > problem data lead to large changes in the solution. > > Your instance in fact is ill conditioned. Glpsol 4.29 gives optimal > value 12, where all KKT optimality conditions are satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 4.72e-12 on row 95 > max.rel.err. = 4.72e-12 on row 95 > High quality > > KKT.PB: max.abs.err. = 7.88e-10 on column 237 > max.rel.err. = 7.88e-10 on column 237 > High quality > > KKT.DE: max.abs.err. = 1.71e-13 on column 166 > max.rel.err. = 8.53e-14 on column 166 > High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 > max.rel.err. = 0.00e+00 on row 0 > High quality > > However, if I convert your instance in MPS format and then run glpsol, > it crashes: > > spx_simplex: warning: numerical instability (primal simplex, phase II) > 583: objval = 1.232678937e+02 infeas = 1.000000000e+00 (0) > 600: objval = 1.357637434e+02 infeas = 6.333149060e-02 (0) > Assertion failed: spx->p != 0 > Error detected in file src\glpspx02.c at line 602 > > Using a newer, more stable version of glp_simplex I managed to solve > your instance; now the optimal value is 170, and KKT conditions are > still satisfied: > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err. = 1.91e-06 on row 181 > max.rel.err. = 1.91e-06 on row 181 > Low quality > > KKT.PB: max.abs.err. = 7.29e-10 on row 86 > max.rel.err. = 7.29e-10 on row 86 > High quality > > KKT.DE: max.abs.err. = 0.00e+00 on column 0 > max.rel.err. = 0.00e+00 on column 0 > High quality > > KKT.DB: max.abs.err. = 0.00e+00 on row 0 > max.rel.err. = 0.00e+00 on row 0 > High quality > >>> >>>> Also neither lpx_adv_basis nor lpx_std_basis >>>> seem to solve the problem from C++ API level. Could anyone please tell >>>> me what I am missing here? >>> >>> Could you provide the code returned by glp_simplex? >> I'm getting > >> PROBLEM HAS UNBOUNDED SOLUTION >> glp_simplex: cannot recover undefined or non-optimal solution > >> and glp_simplex returns 11, i.e. GLP_ENODFS (no dual feasible) > > The lp presolver should be disabled; the reason was explained above. > > -- Dwell not on close decisions, and thus, when you play against dwellers, you will make reciprocal gains in energy conservation and sanity preservation. Tommy Angelo _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
