Opened 4 years ago

Closed 4 years ago

#17867 closed defect (fixed)

Risk of confusion between LPProblem and MixedIntegerLinearProgram

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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) Commit: 5b98d3d61c7b13d89d73dea09947f81d4f9e61be
Dependencies: Stopgaps:

Description (last modified by ncohen)

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/sage-ipython: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 4 years ago by ncohen

  • Authors set to Nathann Cohen
  • 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

New commits:

9ab6ea2trac #17867: Risk of confusion between LPProblem and MixedIntegerLinearProgram

comment:2 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 4 years ago by dimpase

Good idea! No time for reviewing now...

comment:4 Changed 4 years ago by ncohen

  • Description modified (diff)

comment:5 follow-ups: Changed 4 years ago by vdelecroix

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

Vincent

comment:6 in reply to: ↑ 5 ; follow-up: Changed 4 years ago by 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 vice-versa.

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 4 years ago by git

  • Commit changed from 9ab6ea2b4c79e0aa04ccd6a5d6ba2a7e34b78fcd to 5b98d3d61c7b13d89d73dea09947f81d4f9e61be

Branch pushed to git repo; I updated commit sha1. New commits:

5b98d3dtrac #17867: Link from MILP to Interactive Solver

comment:8 in reply to: ↑ 5 Changed 4 years ago by ncohen

Hello,

Could you make a reference in the doc of MixedIntegerLinearProgramming toward InteractiveLPProblem?

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 in ILPP versus the argument nonnegative=True in MILP. problem_type in ILPP versus maximization=True in MILP, etc. Wouldn't it?

Possibly. I never read the code of interactive_simplex_method.

Nathann

comment:9 follow-up: Changed 4 years ago by novoselt

I would prefer a suffix, rather than prefix, but I guess for courses you tell the name to students anyway and with a cross-link 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 4 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

LGTM, thanks, Nathann!

comment:11 in reply to: ↑ 6 ; follow-up: Changed 4 years ago by 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 vice-versa.

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 ; follow-up: Changed 4 years ago by dimpase

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

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/help-glpk/2010-11/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 4 years ago by ncohen

Helloooooooooo !

I would prefer a suffix, rather than prefix, but I guess for courses you tell the name to students anyway and with a cross-link 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 ; follow-up: Changed 4 years ago by 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 ?

Nathann

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by dimpase

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

comment:16 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by 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?

Nathann

comment:17 in reply to: ↑ 16 Changed 4 years ago by dimpase

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 4 years ago by vbraun

  • Branch changed from public/17867 to 5b98d3d61c7b13d89d73dea09947f81d4f9e61be
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.