Fix chaining of MILP constraints

[ncohen]

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

[dimpase]

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

[ncohen]

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

Nathann

[dimpase]

Replying to ncohen:

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]

I'm investigating this.

[jdemeyer]

New commits:

​ba7613b

Fix chained inequalities with non-Sage types

[dimpase]

New commits:

​ba7613b

Fix chained inequalities with non-Sage types

[mkoeppe]

It's not completely fixed. Example:

sage: float(0) <= b[0] <= int(1) <= b[1] <= float(2)
1 <= x_1 <= 2

[jdemeyer]

Allright, let's fix everything on this ticket...

[git]

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

​f41c195

14540 WIP

[git]

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

​3782ec2	Common base class for LinearFunction and LinearConstraint
​682ba3e	Fix chaining of MILP constraints

[jdemeyer]

In the end, I had to rewrite most of the comparison code but still using the ideas of the original code.

[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

(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]

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]

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]

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]

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

[git]

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

​e8d8e67

Improve documentation

[git]

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

​6e10798

Improve documentation

[mkoeppe]

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

[tscrim]

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

[mkoeppe]

Thanks, Travis!

[mkoeppe]

The patchbot complains about decreased coverage, though

[git]

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

​96e133e

Improve __cinit__ and add doctests

[jdemeyer]

Thanks!