Re: [Help-glpk] glpksol default settings

[Marcin Mucha]

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 <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.
>
>



-- 
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