Re: [Help-glpk] Certificates of infeasibility or unboundness

[Andrew Makhorin]

> Oh. Well, Sage already tells when the problem is infeasible thanks to
> GLPK's signals, but I would like something stronger like a proof that
> the LP is indeed infeasible if it is the case, something like a Farkas
> certificate :
> 
> http://en.wikipedia.org/wiki/Farkas'_lemma
> http://www.win.tue.nl/~rudi/farkas_handout.pdf
> 
> That's what I thought glp_get_unbnd_ray was all about ^^;

Currently the glpk simplex solver does not have an api routine to
provide a proof that lp has no primal/dual feasible solution. However,
when glp_simplex returns GLP_ENOFEAS, the final primal infeasible basis
stored back to glp_prob is extremal in the sense that it minimizes an
artificial objective which is the sum of residuals (if the primal
simplex was used). This extremal property does not depend on artificial
objective coefficients, in particular, on scaling factors used; thus,
one can build an artificial row sum a[j]*x[j], where a[j] = -1, if x[j]
violates its lower bound, a[j] = +1, if x[j] violates its upper bound,
and a[j] = 0, if x[j] is feasible, and then use glp_transform_row to
compute corresponding Lagrange multipliers for the final basis. These
multipliers being used as coefficients of a linear combination of lp
constraints will prove primal infeasibility in Farkas' sense. The same
can be used in the dual case to prove unboundedness, i.e. dual
infeasibility. Of course, there must be api routines that peforms such
calculations.