Opened 10 years ago
Closed 9 years ago
#12091 closed defect (fixed)
chained inequalities bug in add_constraint to MixedIntegerLinearProgram
Reported by: | dimpase | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | linear programming | Keywords: | |
Cc: | ncohen, kini, vbraun | 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 9 years ago by
- Cc ncohen kini added
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 5 Changed 9 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 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 9 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 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 9 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 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 9 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 in reply to: ↑ 7 Changed 9 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 9 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 in reply to: ↑ 9 ; follow-up: ↓ 12 Changed 9 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 9 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 in reply to: ↑ 10 Changed 9 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 9 years ago by
AFAIK nothing gets preparsed from the library. The library is pure Python, not "Sage code" (thankfully).
comment:14 in reply to: ↑ 13 Changed 9 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 9 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 9 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 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 9 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 in reply to: ↑ 17 Changed 9 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 9 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 in reply to: ↑ 19 Changed 9 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 9 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 9 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 9 years ago by
This can be closed as a duplicate as soon as #13646 is done.
comment:24 in reply to: ↑ 23 Changed 9 years ago by
comment:25 Changed 9 years ago by
- Cc vbraun added
- Description modified (diff)
- Priority changed from critical to major
- Summary changed from bug in add_constraint to MixedIntegerLinearProgram to chained inequalities bug in add_constraint to MixedIntegerLinearProgram
comment:26 follow-up: ↓ 27 Changed 9 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 in reply to: ↑ 26 Changed 9 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 9 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 in reply to: ↑ 28 Changed 9 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 9 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 9 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 in reply to: ↑ 31 Changed 9 years ago by
- Status changed from new to 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 9 years ago by
Probably won't have time to work on this in the next two weeks...
comment:34 Changed 9 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 9 years ago by
- Milestone changed from sage-5.4 to sage-5.5
- Status changed from needs_info to needs_review
comment:36 Changed 9 years ago by
- Dependencies set to 13650
- Description modified (diff)
- Status changed from needs_review to 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 9 years ago by
- Dependencies changed from 13650 to #13650
comment:38 Changed 9 years ago by
- Reviewers set to Dmitrii Pasechnik
comment:39 follow-up: ↓ 40 Changed 9 years ago by
Fair enough but can you make another ticket about invalid combinations? Otherwise its too easy to forget ;-)
comment:40 in reply to: ↑ 39 Changed 9 years ago by
comment:41 Changed 9 years ago by
- Merged in set to sage-5.5.rc0
- Resolution set to fixed
- Status changed from positive_review to 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