> 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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
