[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] glpksol default settings

From: Haroldo Santos
Subject: Re: [Help-glpk] glpksol default settings
Date: Tue, 29 Jul 2008 13:26:56 -0300


Did you plan to include this new version of glp_simplex in 4.30 ?


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

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

Help-glpk mailing list

Haroldo Gambini Santos
Instituto de Computacao - Universidade Federal Fluminense

reply via email to

[Prev in Thread] Current Thread [Next in Thread]