Re: [Help-glpk] Dual infeasibility

[Andrew Makhorin]

> I have a large LP which I am trying to solve. GLPK
> gives the output like this

> Karush-Kuhn-Tucker optimality conditions:

> KKT.PE: max.abs.err. = 2.25e-011 on row 281
>         max.rel.err. = 3.66e-014 on row 85124
>         High quality

> KKT.PB: max.abs.err. = 9.56e-006 on row 33251
>         max.rel.err. = 1.73e-007 on row 33251
>         Medium quality

> KKT.DE: max.abs.err. = 7.41e-009 on column 47780
>         max.rel.err. = 1.28e-013 on column 34867
>         High quality

> KKT.DB: max.abs.err. = 1.04e+006 on column 14390
>         max.rel.err. = 2.10e+003 on column 25697
>         DUAL SOLUTION IS INFEASIBLE

> End of output

> Also the infeasibility is very small in the primal
> problem (1e-12). I thought that the primal BFS need
> not be Dual feasible unless it is optimal. So why does
> GLPK need dual feasibility before the problem has run
> to optimallity?

Glpk does not need that (until you choose the dual simplex to solve
the problem). Violation of dual feasibility (KKT.DB) means that some
reduced costs have wrong sign, i.e. the current basic solution you
obtained is primal feasible, but dual infeasible, that is, non-optimal.
If you are using glp_simplex, this may mean that the solution process
was prematurely terminated. Try to check the return code.