Fix chaining of MILP constraints

[nathanncohen]

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: int(1) <= b[0] <= int(2)
x_0 <= 2

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: float(0) <= b[0] <= int(1) <= b[1] <= float(2)
1 <= x_1 <= 2

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= 555*b[1] >= 2
2 <= x_0 <= 555*x_1

This can never work due to the way Python handles chained comparisons:

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= 3 <= 4
True

Depends on #20478

CC: @vbraun @dimpase @mkoeppe @videlec @tscrim

Component: linear programming

Author: Jeroen Demeyer

Branch/Commit: 96e133e

Reviewer: Matthias Koeppe, Travis Scrimshaw

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

[dimpase]

comment:1

In a script - do you mean a Python script, not Sage script, right?

[nathanncohen]

comment:2

Well, in any script that does not wrap integers with Integer(). So a .py that you load with %runfile is ok !

Nathann

[dimpase]

comment:3

Replying to @nathanncohen:

Well, in any script that does not wrap integers with Integer(). So a .py that you load with %runfile is ok !

Nathann

and it's not only int, but float, too, that gives this problem.

[jdemeyer]

comment:10

I'm investigating this.

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Branch: u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly

[jdemeyer]

Commit: ba7613b

[jdemeyer]

New commits:

ba7613b

Fix chained inequalities with non-Sage types

[dimpase]

New commits:

ba7613b

Fix chained inequalities with non-Sage types

[mkoeppe]

comment:25

It seems to work, except for bizarre behavior if one does try to chain in comparisons between constants.

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= 2 <= 2
True
sage: 0<=b[0]<=b[0]<=b[0]<=1
0 <= x_0 <= 2 <= x_0 <= x_0 <= 1

(The documentation should probably explain what is expected to work and what is not!)

I note that the unrelated comparison-hack code for SR silently throws away chained inequalities.

sage: var('x')
x
sage: x <= 2 <= 3
x <= 2
sage: x <= 2 <= x
x <= 2

Also, should add_constraint allow the user to add tautological constraints like this:

sage: p = MixedIntegerLinearProgram()
sage: p.add_constraint(0<=0)
ValueError: argument must be a linear function or constraint, got True

Someone should probably review your changes to Parent before this ticket is set to positive_review.

[jdemeyer]

comment:26

Replying to @mkoeppe:

It seems to work, except for bizarre behavior if one does try to chain in comparisons between constants.

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= 2 <= 2
True
sage: 0<=b[0]<=b[0]<=b[0]<=1
0 <= x_0 <= 2 <= x_0 <= x_0 <= 1

There are theoretical limits to what can work without fundamentally changing Python (or the preparser if you want to go that way), that's why it is called a "hack".

I could add a bit of documentation, although a full explanation would probably be too technical.

[mkoeppe]

comment:27

Replying to @jdemeyer:

I could add a bit of documentation, although a full explanation would probably be too technical.

It would suffice to explain that you can chain linear expressions with the same comparison, and also use constants at the very left hand side and the very right hand side. If the user tries anything beyond that, there's either an error or weirdness.

[jdemeyer]

comment:28

Replying to @mkoeppe:

Replying to @jdemeyer:

I could add a bit of documentation, although a full explanation would probably be too technical.

It would suffice to explain that you can chain linear expressions with the same comparison, and also use constants at the very left hand side and the very right hand side. If the user tries anything beyond that, there's either an error or weirdness.

Constants in the middle also work, just not two constants next to eachother. For example, b[0] <= 0 <= b[1] works as expected.

[mkoeppe]

comment:29

I know, it was just a suggestion how you could simplify the story when you write that documentation.

[jdemeyer]

Changed reviewer from Matthias Köppe to Matthias Koeppe

[sagetrac-git]

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

e8d8e67

Improve documentation

[sagetrac-git]

Changed commit from 682ba3e to e8d8e67

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6e10798

Improve documentation

[sagetrac-git]

Changed commit from e8d8e67 to 6e10798

[mkoeppe]

comment:33

Looks good to me, but the changes to Parent still need independent review.

[tscrim]

Changed reviewer from Matthias Koeppe to Matthias Koeppe, Travis Scrimshaw

[tscrim]

comment:35

The changes in Parent look good to me. If everything else is good, then this would be a positive review.

[mkoeppe]

comment:36

Thanks, Travis!

[mkoeppe]

comment:38

The patchbot complains about decreased coverage, though

[sagetrac-git]

Changed commit from 6e10798 to 96e133e

[sagetrac-git]

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

96e133e

Improve `__cinit__` and add doctests

[jdemeyer]

comment:42

Thanks!

[vbraun]

Changed branch from u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly to 96e133e