chained inequalities bug in add_constraint to MixedIntegerLinearProgram

[dimpase]

This ticket was originally started to address problems now dealt with in #13646. Still, the following (chained inequalities don't work) needs to be fixed:

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[0] <= b[1] <= 2  # This is not ok
x_1 <= 2
sage: (b[0] <= b[1] <= 2).constraints # Not ok
[x_1, 2]
sage: 1 >= b[1] >= 2*b[0] # Not ok (note that without #13646 this returns False)
2 x_0 <= x_1
sage: b[2] >= b[1] >= 2*b[0]  # Not ok
2 x_0 <= x_1

See also this ​sage-support thread.

Apply

• trac_12091_constraints_parents.patch​

[ncohen]

I spent days already on this problem, so I should at least update the ticket. This does not work because of.... that :

sage: p = MixedIntegerLinearProgram()
sage: b = p.new_variable()
sage: b[2] + b[4] >= 5
5 <= x_0 +x_1
sage: 5 <= b[2] + b[4]
True

It is as easy as that. And of course, calling p.add_constraint(True) can not do anything useful. That comes from the fact that the way it is implemented the comparison methods I wrote for the LP variables are totally ignored when there is an integer on the left of the equation.

I went through hell (aka the coercion system) to make it work, and after getting back from hell (writing new classes, using categories, parents objets, elements objects, ...) Sage finally understood that it has to coerce integers to "LinearFunction?" objects before applying the <= operation.

I was happy at this point. And then I noticed that when I typed 3*b[i] in Sage, it first converted the "3" to a LinearFunction? object and then tried to multiply linear functions between themselves. And multiply linear functions is *never* a good idea.

So unless there is a magical way to make it work (without destroying all the code... I mean, even reaching that former point amounted to something like 100 additional lines of code totally exclusively dealing with categories and coercion), I'd stand for big "DO NOT PUT AN INTEGER BY ITSELF ON THE LEFT SIDE OF A LP INEQUALITY" in the doc.

But I'd prefer to find a magical way, of course..

Nathann

[dimpase]

I might be clueless, but this asks a modification of the Sage pre-parser. The pre-parser might be able to add the crap necessary for the Hell (aka coersion framework) to freeze over and do the right thing...

Dima

[ppurka]

Replying to dimpase:

I might be clueless, but this asks a modification of the Sage pre-parser. The pre-parser might be able to add the crap necessary for the Hell (aka coersion framework) to freeze over and do the right thing...

Not sure about the preparser. But I feel that at least some of the bugs (the examples I added) can be fixed by modifying the Linear* classes I mentioned. I had been hacking it for about a day, but I haven't yet got the right solution. The constants are indeed way more trickier to handle, since there seems to be no way of knowing when we have normal inequalities and when we have LP ones.

[dimpase]

Replying to ppurka:

The constants are indeed way more trickier to handle, since there seems to be no way of knowing when we have normal inequalities and when we have LP ones.

How come? The LP inequalities have LP variables. So one of the tokens will be such a variable...

[ppurka]

Replying to dimpase:

How come? The LP inequalities have LP variables. So one of the tokens will be such a variable...

My understanding is this:

When you start with 5 <= b[0] your program will see the number 5 not an object from the class LinearConstraint or LinearFunction. So, LinearConstraint.__le__ won't be called. This is ok when you have the opposite b[0] >= 5.

[dimpase]

Replying to ppurka:

Replying to dimpase:

How come? The LP inequalities have LP variables. So one of the tokens will be such a variable...

My understanding is this:

When you start with 5 <= b[0] your program will see the number 5 not an object from the class LinearConstraint or LinearFunction. So, LinearConstraint.__le__ won't be called. This is ok when you have the opposite b[0] >= 5.

OK, this just means that the preparser should keep looking further if he sees a constant... IMHO it's some kind of basic compiler/interpreter piece of technology.

[ncohen]

Why do you see the problem at the preparser level ? This kind of lines can also appear fron the inside of Sage's code, where the preparser does nothing.. Or am I mistaken ?

Nathann

[dimpase]

Replying to ncohen:

Why do you see the problem at the preparser level ? This kind of lines can also appear fron the inside of Sage's code, where the preparser does nothing.. Or am I mistaken ?

Nothing? Why? Surely you can use symbolic functions in Sage library code, why not? It gets preparsed all right.

[ncohen]

Oh, I thought the preparser was the piece of code that replaced 5 by Integer(5) when using the console, and that you had to rely on yourself when writing code from the inside of Sage. That's why I was convinced that the only way out of this mess was to deal with the coercion system.

Nathann

[ppurka]

Replying to dimpase:

Replying to ncohen:

Why do you see the problem at the preparser level ? This kind of lines can also appear fron the inside of Sage's code, where the preparser does nothing.. Or am I mistaken ?

Nothing? Why? Surely you can use symbolic functions in Sage library code, why not? It gets preparsed all right.

Actually no. Not everything gets preparsed. I ran into this problem not long ago, where the ^ wasn't preparsed since it was in a separate file I was importing.

[kini]

AFAIK nothing gets preparsed from the library. The library is pure Python, not "Sage code" (thankfully).

[dimpase]

Replying to kini:

AFAIK nothing gets preparsed from the library. The library is pure Python, not "Sage code" (thankfully).

I recall in our MTH213 code we certainly used symbolic functions inside .py files. I might be delusional, however...

[ncohen]

Well I guess you can, but I don't think the manipulation of symbolic variables requires the preparser to do its job. I mean, adding LP variables is already some kind of symbolic computation and all it requires is to define add, mul, etc ...

Nathann

[kini]

dimpase: if you mean the syntax

f(x) = x^2

then no, we definitely did not use it in .py files :) But you certainly don't NEED the preparser for any Sage functionality. Well, unless you count the preparser itself as "Sage functionality". For example the above is equivalent to

f = (x^2).function(x)

[dimpase]

Replying to kini:

we definitely did not use it in .py files :) But you certainly don't NEED the preparser for any Sage functionality. Well, unless you count the preparser itself as "Sage functionality".

well, anyway. Actually, I don't see why Sage library files can't be .sage file, is it some kind of religion? (OK, you'd need to preparse them once, I guess).

It's obviously makes things unnecessarily verbose to rely upon Python's idea of what a well-formed mathematical expression might be.

[ncohen]

well, anyway. Actually, I don't see why Sage library files can't be .sage file, is it some kind of religion?

Yeah, at some point we stopped blaming God for everything. We should do it again :-D

It's obviously makes things unnecessarily verbose to rely upon Python's idea of what a well-formed mathematical expression might be.

+1

That's precisely why I had to create a "Sum" function for LP variables. Because I refused to add n variables in n^{2 times, and that it is the only way to do it with add methods. And this "Sum" method fixes the problem but is a bad solution.}

Nathann

[kini]

I disagree. The library should remain Python because "Sage code" is not a well defined language. In fact I would go so far to say that it is a complete ad-hoc hash. I try to avoid using it whenever I can.

Nathann: I don't see how that is an argument for including .sage files in the Sage library... or maybe it wasn't meant that way?

[dimpase]

Replying to kini:

I disagree. The library should remain Python because "Sage code" is not a well defined language. In fact I would go so far to say that it is a complete ad-hoc hash. I try to avoid using it whenever I can.

let's make it well-defined then!

[ncohen]

Nathann: I don't see how that is an argument for including .sage files in the Sage library... or maybe it wasn't meant that way?

Oh. Well, my "+1" was just about Dima's remark that what we were fighting in this situation was precisely Python's management of + / * - operators... Looks like in this situation it is clearly our main problem :-)

Nathann

[ppurka]

The problem with the a <= b <= c is actually a problem with python. According to ​this, chained inequalities behave as follows:

# Trying to do x < y < z
             temp1 = x < y
             if temp1:
               return y < z
             else:
               return temp1

According to one of my colleagues this behavior is different in python-3 (and that python-3 has the behavior we want), but I haven't checked (I will need to install python-3).

One workaround is to explicitly group the inequalities. So, instead of inputting a <= b <= c, if we do (a <= b) <= c then it works. Since we are not moving to python-3 any time soon, the documentation should be updated to either discourage chained inequalities or to use explicitly grouped chained inequalities.

[dimpase]

This can be closed as a duplicate as soon as #13646 is done.

[ppurka]

Replying to dimpase:

This can be closed as a duplicate as soon as #13646 is done.

Nope. The problem with the chained inequalities still remains.

[vbraun]

Patch fixes chained constraints:

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

[dimpase]

Replying to vbraun:

Patch fixes chained constraints:

indeed! What about more convoluted cases:

sage: b[0] <= 555/11*b[1] >= 2
2 <= x_0 <= 555/11*x_1
sage: b[0] <= 555/11*b[1] == 2
555/11*x_1 == 2

the 1st one ought to become 2 inequalities, and the 2nd an inequality and an equation. In both cases, the behaviour is rather strange...

Well, I don't know how easy is to make these work, or at least throw an error.

[vbraun]

I agree that it is odd behavior. The whole idea of automatically converting all inequalities into less-or-equal is broken, even before my patch:

sage: (b[0] <= b[1]) >= b[2]
x_2 <= x_0 <= x_1

Inequalities need to remember >= vs. <= for us to be able to raise an error. The second example is a bug in my patch.

[dimpase]

Replying to vbraun:

I agree that it is odd behavior. The whole idea of automatically converting all inequalities into less-or-equal is broken, even before my patch:

sage: (b[0] <= b[1]) >= b[2]
x_2 <= x_0 <= x_1

Inequalities need to remember >= vs. <= for us to be able to raise an error.

Anything wrong with having that much more in the inequalities class?

Potentially one would also want to have < and > and a proper integration with Sage's polyhedra.

Your patch also inspires a grand plan for ​linear matrix inequalities in Sage...

[ppurka]

I think mixed chained inequalities/equalities could be errored out. That would ensure that such obtuse inputs are taken care of.

The reason for providing chained inequalities is to actually give inequalities in the form 2 <= x[0] <= 3 or 2 >= x[1] >= 1, instead of having to set them separately. These types of inequalities are quite common to encounter, and it helps the user if the mathematical expressions can be transferred to sage in a straightforward manner.

Examples like x[0] <= x[1] >= x[2] or x[0] <= x[1] == 2 are quite unusual. I have never seen such expressions come up naturally. The first example, for instance, says nothing about the relation between x[0] and x[2] and hence one would typically never encounter inequations (written) like that.

[vbraun]

I agree that one should raise an error. But to be able to do this you must not auto-convert to less-or-equal. And thats definitely doable ;-)

[dimpase]

Replying to vbraun:

I agree that one should raise an error. But to be able to do this you must not auto-convert to less-or-equal. And thats definitely doable ;-)

Hi Volker, will you work on this? Just to indicate the ticket status right.

[vbraun]

Probably won't have time to work on this in the next two weeks...

[vbraun]

Updated patch

[vbraun]

I've removed the "cdef double c" in show(), so the following works:

            sage: p = MixedIntegerLinearProgram(solver= 'ppl')
            sage: x = p.new_variable()
            sage: p.set_objective(x[1] + 1/2*x[2])
            sage: p.add_constraint(-3/5*x[1] + 2/7*x[2], max=2/5)
            sage: p.show()
            Maximization:
              x_0 + 1/2 x_1
            Constraints:
              constraint_0: -3/5 x_0 + 2/7 x_1 <= 2/5
            Variables:
              x_0 is a continuous variable (min=0, max=+oo)
              x_1 is a continuous variable (min=0, max=+oo)

[dimpase]

As far as I am concerned, better parsing of things like x[0] <= x[1] >= x[2] or x[0] <= x[1] == 2 can wait till another ticket.

[vbraun]

Fair enough but can you make another ticket about invalid combinations? Otherwise its too easy to forget ;-)

[dimpase]

Replying to vbraun:

Fair enough but can you make another ticket about invalid combinations? Otherwise its too easy to forget ;-)

Sure! Please see #13696.