Opened 11 years ago
Closed 10 years ago
#12091 closed defect (fixed)
chained inequalities bug in add_constraint to MixedIntegerLinearProgram
Reported by: | Dima Pasechnik | Owned by: | Nathann Cohen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | linear programming | Keywords: | |
Cc: | Nathann Cohen, Keshav Kini, Volker Braun | Merged in: | sage-5.5.rc0 |
Authors: | Volker Braun | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13650 | Stopgaps: |
Description (last modified by )
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
Attachments (1)
Change History (42)
comment:1 Changed 11 years ago by
Cc: | Nathann Cohen Keshav Kini added |
---|
comment:2 Changed 11 years ago by
comment:3 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:4 follow-up: 5 Changed 11 years ago by
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 follow-up: 6 Changed 11 years ago by
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.
comment:6 follow-up: 7 Changed 11 years ago by
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...
comment:7 follow-up: 8 Changed 11 years ago by
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
.
comment:8 Changed 11 years ago by
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 classLinearConstraint
orLinearFunction
. So,LinearConstraint.__le__
won't be called. This is ok when you have the oppositeb[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
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 follow-up: 12 Changed 11 years ago by
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.
comment:11 Changed 11 years ago by
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 Changed 11 years ago by
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.
comment:13 follow-up: 14 Changed 11 years ago by
AFAIK nothing gets preparsed from the library. The library is pure Python, not "Sage code" (thankfully).
comment:14 Changed 11 years ago by
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...
comment:15 Changed 11 years ago by
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
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 follow-up: 18 Changed 11 years ago by
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.
comment:18 Changed 11 years ago by
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
comment:19 follow-up: 20 Changed 11 years ago by
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 Changed 11 years ago by
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!
comment:21 Changed 11 years ago by
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
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
This can be closed as a duplicate as soon as #13646 is done.
comment:24 Changed 10 years ago by
comment:25 Changed 10 years ago by
Cc: | Volker Braun added |
---|---|
Description: | modified (diff) |
Priority: | critical → major |
Summary: | bug in add_constraint to MixedIntegerLinearProgram → chained inequalities bug in add_constraint to MixedIntegerLinearProgram |
comment:26 follow-up: 27 Changed 10 years ago by
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 Changed 10 years ago by
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.
comment:28 follow-up: 29 Changed 10 years ago by
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 Changed 10 years ago by
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_1Inequalities 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
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
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 Changed 10 years ago by
Status: | new → needs_info |
---|
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.
comment:33 Changed 10 years ago by
Probably won't have time to work on this in the next two weeks...
comment:34 Changed 10 years ago by
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)
comment:35 Changed 10 years ago by
Milestone: | sage-5.4 → sage-5.5 |
---|---|
Status: | needs_info → needs_review |
comment:36 Changed 10 years ago by
Dependencies: | → 13650 |
---|---|
Description: | modified (diff) |
Status: | 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
Dependencies: | 13650 → #13650 |
---|
comment:38 Changed 10 years ago by
Authors: | → Volker Braun |
---|---|
Reviewers: | → Dmitrii Pasechnik |
comment:39 follow-up: 40 Changed 10 years ago by
Fair enough but can you make another ticket about invalid combinations? Otherwise its too easy to forget ;-)
comment:40 Changed 10 years ago by
comment:41 Changed 10 years ago by
Merged in: | → sage-5.5.rc0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
I spent days already on this problem, so I should at least update the ticket. This does not work because of.... that :
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