#17867: Risk of confusion between LPProblem and MixedIntegerLinearProgram
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner:
Type: defect | Status: positive_review
Priority: major | Milestone: sage-6.6
Component: linear | Resolution:
programming | Merged in:
Keywords: | Reviewers: Andrey Novoseltsev
Authors: Nathann Cohen | Work issues:
Report Upstream: N/A | Commit:
Branch: public/17867 | 5b98d3d61c7b13d89d73dea09947f81d4f9e61be
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dimpase):
Replying to [comment:14 ncohen]:
> > Commercial solvers like CPLEX and GUROBI do provide these certs, as
well as CVXOPT, but GLPK apparently not, cf
https://lists.gnu.org/archive/html/help-glpk/2010-11/msg00062.html
> > Apparently this is still the case, although the latter conversation
took place in 2010.
>
> We can ask again. More importantly, how do you think that such
certificates should be returned to the user ?
given the plethora of different formulations of LPs, it's a bit hard do
say. If we talk about canonical primal-dual pair, i.e. `max c*x s.t.
Ax<=b` and `min b*y s.t. yA=c`, then optimality is the complementary
slackness
(http://en.wikipedia.org/wiki/Linear_programming#Complementary_slackness),
so that one should give a primal and a dual optimal solution (so that the
user can check that they satisfy it).
for ineasibility, a Farkas certificate (i.e. coefficients of a nonnegative
linear
combination of inequalities producing a contradiction) seems to be an
obvious choice.
--
Ticket URL: <http://trac.sagemath.org/ticket/17867#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
