Opened 11 years ago

Closed 10 years ago

chained inequalities bug in add_constraint to MixedIntegerLinearProgram

Reported by: Owned by: Dima Pasechnik Nathann Cohen major sage-5.5 linear programming Nathann Cohen, Keshav Kini, Volker Braun sage-5.5.rc0 Volker Braun Dmitrii Pasechnik N/A #13650

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

Apply

comment:1 Changed 11 years ago by Dima Pasechnik

Cc: Nathann Cohen Keshav Kini added

comment:2 Changed 11 years ago by Nathann Cohen

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

comment:3 Changed 11 years ago by Punarbasu Purkayastha

Description: modified (diff)

comment:4 follow-up:  5 Changed 11 years ago by Dima Pasechnik

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

comment:5 in reply to:  4 ; follow-up:  6 Changed 11 years ago by Punarbasu Purkayastha

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.

comment:6 in reply to:  5 ; follow-up:  7 Changed 11 years ago by Dima Pasechnik

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

comment:7 in reply to:  6 ; follow-up:  8 Changed 11 years ago by Punarbasu Purkayastha

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

comment:8 in reply to:  7 Changed 11 years ago by Dima Pasechnik

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.

comment:9 follow-up:  10 Changed 11 years ago by Nathann Cohen

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

comment:10 in reply to:  9 ; follow-up:  12 Changed 11 years ago by Dima Pasechnik

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.

comment:11 Changed 11 years ago by Nathann Cohen

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

comment:12 in reply to:  10 Changed 11 years ago by Punarbasu Purkayastha

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.

comment:13 follow-up:  14 Changed 11 years ago by Keshav Kini

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

comment:14 in reply to:  13 Changed 11 years ago by Dima Pasechnik

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

comment:15 Changed 11 years ago by Nathann Cohen

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

comment:16 follow-up:  17 Changed 11 years ago by Keshav 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)
```

comment:17 in reply to:  16 ; follow-up:  18 Changed 11 years ago by Dima Pasechnik

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.

comment:18 in reply to:  17 Changed 11 years ago by Nathann Cohen

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

comment:19 follow-up:  20 Changed 11 years ago by Keshav 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?

comment:20 in reply to:  19 Changed 11 years ago by Dima Pasechnik

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!

comment:21 Changed 11 years ago by Nathann Cohen

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

comment:22 Changed 11 years ago by Punarbasu Purkayastha

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.

comment:23 follow-up:  24 Changed 10 years ago by Dima Pasechnik

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

comment:24 in reply to:  23 Changed 10 years ago by Punarbasu Purkayastha

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

Nope. The problem with the chained inequalities still remains.

comment:25 Changed 10 years ago by Dima Pasechnik

Cc: Volker Braun added modified (diff) critical → major bug in add_constraint to MixedIntegerLinearProgram → chained inequalities bug in add_constraint to MixedIntegerLinearProgram

comment:26 follow-up:  27 Changed 10 years ago by Volker Braun

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

comment:27 in reply to:  26 Changed 10 years ago by Dima Pasechnik

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.

comment:28 follow-up:  29 Changed 10 years ago by Volker Braun

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.

comment:29 in reply to:  28 Changed 10 years ago by Dima Pasechnik

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

comment:30 Changed 10 years ago by Punarbasu Purkayastha

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.

comment:31 follow-up:  32 Changed 10 years ago by Volker Braun

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 ;-)

comment:32 in reply to:  31 Changed 10 years ago by Dima Pasechnik

Status: new → needs_info

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.

comment:33 Changed 10 years ago by Volker Braun

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

Updated patch

comment:34 Changed 10 years ago by Volker Braun

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

comment:35 Changed 10 years ago by Dima Pasechnik

Milestone: sage-5.4 → sage-5.5 needs_info → needs_review

comment:36 Changed 10 years ago by Dima Pasechnik

Dependencies: → 13650 modified (diff) needs_review → positive_review

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.

comment:37 Changed 10 years ago by Jeroen Demeyer

Dependencies: 13650 → #13650

comment:38 Changed 10 years ago by Jeroen Demeyer

Authors: → Volker Braun → Dmitrii Pasechnik

comment:39 follow-up:  40 Changed 10 years ago by Volker Braun

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