Opened 8 years ago

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

Attachments (1)

trac_12091_constraints_parents.patch (71.4 KB) - added by vbraun 7 years ago.
Updated patch

Download all attachments as: .zip

Change History (42)

comment:1 Changed 8 years ago by dimpase

  • Cc ncohen kini added

comment:2 Changed 8 years ago by 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

comment:3 Changed 8 years ago by ppurka

  • Description modified (diff)

comment:4 follow-up: Changed 8 years ago by 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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 8 years ago by 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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 8 years ago by 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...

comment:7 in reply to: ↑ 6 ; follow-up: Changed 8 years ago by 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.

comment:8 in reply to: ↑ 7 Changed 8 years ago by 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.

comment:9 follow-up: Changed 8 years ago by 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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 8 years ago by 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.

comment:11 Changed 8 years ago by 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

comment:12 in reply to: ↑ 10 Changed 8 years ago by 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.

comment:13 follow-up: Changed 8 years ago by kini

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

comment:14 in reply to: ↑ 13 Changed 8 years ago by 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...

comment:15 Changed 8 years ago by 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

comment:16 follow-up: Changed 8 years ago by 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: Changed 8 years ago by 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.

comment:18 in reply to: ↑ 17 Changed 8 years ago by 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 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: Changed 8 years ago by 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 8 years ago by 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!

comment:21 Changed 8 years ago by 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

comment:22 Changed 7 years ago by 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.

comment:23 follow-up: Changed 7 years ago by dimpase

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

comment:24 in reply to: ↑ 23 Changed 7 years ago by 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.

comment:25 Changed 7 years ago by dimpase

  • 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: Changed 7 years ago by 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

comment:27 in reply to: ↑ 26 Changed 7 years ago by 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.

comment:28 follow-up: Changed 7 years ago by 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.

comment:29 in reply to: ↑ 28 Changed 7 years ago by 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...

comment:30 Changed 7 years ago by 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.

comment:31 follow-up: Changed 7 years ago by 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 ;-)

comment:32 in reply to: ↑ 31 Changed 7 years ago by dimpase

  • 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 7 years ago by vbraun

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

Changed 7 years ago by vbraun

Updated patch

comment:34 Changed 7 years ago by 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)

comment:35 Changed 7 years ago by dimpase

  • Milestone changed from sage-5.4 to sage-5.5
  • Status changed from needs_info to needs_review

comment:36 Changed 7 years ago by dimpase

  • 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 7 years ago by jdemeyer

  • Dependencies changed from 13650 to #13650

comment:38 Changed 7 years ago by jdemeyer

  • Authors set to Volker Braun
  • Reviewers set to Dmitrii Pasechnik

comment:39 follow-up: Changed 7 years ago by vbraun

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

comment:40 in reply to: ↑ 39 Changed 7 years ago by 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.

comment:41 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.5.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.