On Tue, Jul 29, 2008 at 10:53 AM, Andrew Makhorin
<address@hidden> 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.