Risk of confusion between LPProblem and MixedIntegerLinearProgram

[nathanncohen]

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

CC: @dimpase @videlec @tscrim @novoselt

Component: linear programming

Author: Nathann Cohen

Branch/Commit: 5b98d3d

Reviewer: Andrey Novoseltsev

Issue created by migration from https://trac.sagemath.org/ticket/17867

[nathanncohen]

Commit: 9ab6ea2

[nathanncohen]

Branch: public/17867

[nathanncohen]

Author: Nathann Cohen

[nathanncohen]

New commits:

9ab6ea2

trac #17867: Risk of confusion between LPProblem and MixedIntegerLinearProgram

[dimpase]

comment:3

Good idea! No time for reviewing now...

[videlec]

comment:5

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

[dimpase]

comment:6

Replying to @videlec:

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

[sagetrac-git]

Changed commit from 9ab6ea2 to 5b98d3d

[sagetrac-git]

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

5b98d3d

trac #17867: Link from MILP to Interactive Solver

[nathanncohen]

comment:8

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

[novoselt]

comment:9

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)

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

comment:10

LGTM, thanks, Nathann!

[novoselt]

comment:11

Replying to @dimpase:

Replying to @videlec:

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?

[dimpase]

comment:12

Replying to @novoselt:

Replying to @dimpase:

Replying to @videlec:

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.

[nathanncohen]

comment:13

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

[nathanncohen]

comment:14

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

[dimpase]

comment:15

Replying to @nathanncohen:

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.

[nathanncohen]

comment:16

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

[dimpase]

comment:17

Replying to @nathanncohen:

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

[vbraun]

Changed branch from public/17867 to 5b98d3d