Opened 7 years ago
Closed 7 years ago
#17867 closed defect (fixed)
Risk of confusion between LPProblem and MixedIntegerLinearProgram
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  linear programming  Keywords:  
Cc:  dimpase, vdelecroix, tscrim, novoselt  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Andrey Novoseltsev 
Report Upstream:  N/A  Work issues:  
Branch:  5b98d3d (Commits, GitHub, GitLab)  Commit:  5b98d3d61c7b13d89d73dea09947f81d4f9e61be 
Dependencies:  Stopgaps: 
Description (last modified by )
Ticket #14288 added a feature meant for educational purposes only which can *very easily* be confused with Sage's support of Linear Programming, as the two classes it creates are named LPProblem and LPProblemStandardForm *AND* imported in the global namespace.
That's suicidal.
With this branch, the two classes are renamed to something more meaningful, pointers are added toward MixedIntegerLinearProgram
, and the old import are deprecated.
sage: P = LPProblem(A, b, c, ["C", "B"], variable_type=">=") /home/ncohen/.Sage/src/bin/sageipython:1: DeprecationWarning: This class meant for **educational purposes only** has been renamed to InteractiveLPProblem See http://trac.sagemath.org/17867 for details. #!/usr/bin/env python
Nathann
Change History (18)
comment:1 Changed 7 years ago by
 Branch set to public/17867
 Cc dimpase vdelecroix tscrim novoselt added
 Commit set to 9ab6ea2b4c79e0aa04ccd6a5d6ba2a7e34b78fcd
 Component changed from PLEASE CHANGE to linear programming
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to defect
comment:2 Changed 7 years ago by
 Description modified (diff)
comment:3 Changed 7 years ago by
Good idea! No time for reviewing now...
comment:4 Changed 7 years ago by
 Description modified (diff)
comment:5 followups: ↓ 6 ↓ 8 Changed 7 years ago by
Could you make a reference in the doc of MixedIntegerLinearProgramming
toward InteractiveLPProblem
? People might be delighted to have an interactive object to learn more about the black box! Though it is only about float linear programming isn't it?
And (not for this ticket) it would be cool if the arguments were compatible: namely variable_type
being either <=
, >=
or the empty string in ILPP
versus the argument nonnegative=True
in MILP
. problem_type
in ILPP
versus maximization=True
in MILP
, etc. Wouldn't it?
And last but not the least: we can use the class ILPP
to cross check the validity of (float) MILP
and viceversa.
Vincent
comment:6 in reply to: ↑ 5 ; followup: ↓ 11 Changed 7 years ago by
Replying to vdelecroix:
And last but not the least: we can use the class
ILPP
to cross check the validity of (float)MILP
and viceversa.
I mentioned some time ago that there is a way to get proper certificates of optimality/infeasibility for LPs (cf Farkas lemma, etc), and it ought to be in Sage...
comment:7 Changed 7 years ago by
 Commit changed from 9ab6ea2b4c79e0aa04ccd6a5d6ba2a7e34b78fcd to 5b98d3d61c7b13d89d73dea09947f81d4f9e61be
Branch pushed to git repo; I updated commit sha1. New commits:
5b98d3d  trac #17867: Link from MILP to Interactive Solver

comment:8 in reply to: ↑ 5 Changed 7 years ago by
Hello,
Could you make a reference in the doc of
MixedIntegerLinearProgramming
towardInteractiveLPProblem
?
Done.
People might be delighted to have an interactive object to learn more about the black box! Though it is only about float linear programming isn't it?
I expect.
And (not for this ticket) it would be cool if the arguments were compatible: namely
variable_type
being either<=
,>=
or the empty string inILPP
versus the argumentnonnegative=True
inMILP
.problem_type
inILPP
versusmaximization=True
inMILP
, etc. Wouldn't it?
Possibly. I never read the code of interactive_simplex_method
.
Nathann
comment:9 followup: ↓ 13 Changed 7 years ago by
I would prefer a suffix, rather than prefix, but I guess for courses you tell the name to students anyway and with a crosslink it is easy to discover.
Regarding parameters being the same or not  please don't do it here to avoid breaking anything, it will require careful changes in documentation. And in general the behaviour is different enough that sameness of input does not matter much, so I'd prefer to not touch it at all. What would be nice to have are conversion functions between regular and educational versions, but when I was working on them I was hitting corner cases bugs in MILP and never finished. Will add to my todo list, especially if I get to teach this course in May/June?.
Regarding types: the education version actually works best with exact rings like QQ. For floating point there is nothing to deal with degeneracy, which is actually nice for education: https://sage373.math.ualberta.ca/home/pub/31/ (takes a while to process formulas)
comment:10 Changed 7 years ago by
 Reviewers set to Andrey Novoseltsev
 Status changed from needs_review to positive_review
LGTM, thanks, Nathann!
comment:11 in reply to: ↑ 6 ; followup: ↓ 12 Changed 7 years ago by
Replying to dimpase:
Replying to vdelecroix:
And last but not the least: we can use the class
ILPP
to cross check the validity of (float)MILP
and viceversa.I mentioned some time ago that there is a way to get proper certificates of optimality/infeasibility for LPs (cf Farkas lemma, etc), and it ought to be in Sage...
Definitely, and these certificates are produced for free when using simplex method, one should just get them out  do solvers interfaces from Sage support providing them?
comment:12 in reply to: ↑ 11 ; followup: ↓ 14 Changed 7 years ago by
Replying to novoselt:
Replying to dimpase:
Replying to vdelecroix:
And last but not the least: we can use the class
ILPP
to cross check the validity of (float)MILP
and viceversa.I mentioned some time ago that there is a way to get proper certificates of optimality/infeasibility for LPs (cf Farkas lemma, etc), and it ought to be in Sage...
Definitely, and these certificates are produced for free when using simplex method, one should just get them out  do solvers interfaces from Sage support providing them?
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/helpglpk/201011/msg00062.html Apparently this is still the case, although the latter conversation took place in 2010.
Not sure about PPL.
comment:13 in reply to: ↑ 9 Changed 7 years ago by
Helloooooooooo !
I would prefer a suffix, rather than prefix, but I guess for courses you tell the name to students anyway and with a crosslink it is easy to discover.
Yesyes. I hope that this will not change too much on your side, and that nobody will get to one class when (s)he should be working with the other.
Thanks for the review,
Nathann
comment:14 in reply to: ↑ 12 ; followup: ↓ 15 Changed 7 years ago by
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/helpglpk/201011/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 ?
Nathann
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 7 years ago by
Replying to 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/helpglpk/201011/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 primaldual 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.
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 7 years ago by
for ineasibility, a Farkas certificate (i.e. coefficients of a nonnegative linear combination of inequalities producing a contradiction) seems to be an obvious choice.
This is what I am asking. How do we return that? As list of floats, and that's it?
Nathann
comment:17 in reply to: ↑ 16 Changed 7 years ago by
Replying to ncohen:
for ineasibility, a Farkas certificate (i.e. coefficients of a nonnegative linear combination of inequalities producing a contradiction) seems to be an obvious choice.
This is what I am asking. How do we return that? As list of floats, and that's it?
floats, or the other appropriate base ring (e.g. rationals for PPL).
Anything that maps correctly into the list of constraints would do.
Nathann
comment:18 Changed 7 years ago by
 Branch changed from public/17867 to 5b98d3d61c7b13d89d73dea09947f81d4f9e61be
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #17867: Risk of confusion between LPProblem and MixedIntegerLinearProgram