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

[Nathann Cohen]

Hello Andrew !!

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

Thank you for your answer ! You make it sound like this is no more
than a 10 minutes work :-)

I do not get your last sentence though "Of course, there must be api
routines that peforms such calculations.". Do you mean "there should"
? Along you answer, you already pointed me to the names of the
functions I would need like glp_transform_row...

Now, it is true that my intent was to write such a code in Sage, but
it is hardly where it belongs. That's shame there is no dedicated
function for this in GLPK : would you think it worth spending a few
nights trying to write a patch for GLPK ? I do not know its code, so I
don't expect to be able to produce it within the month, but it would
definitely be smarter than writing it inside of Sage's source code
where nobody can reuse it ....

Thank you again ! :-)

Nathann