Bug in p.add_constraint (when input is True/False)

[nathanncohen]

That awful thing again. See bug report at :
https://groups.google.com/d/topic/sage-support/VVTWhE0w7i0/discussion

The problem is that the linear functions need to integrate with the rest of sage to play nice. The patched mip.pyx adds a parent class for linear functions and suitable coercion and rich comparison. Now the following works as expected:

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: x[1] >= 10
10 <= x_0
sage: 10 <= x[1]
10 <= x_0

Apply attachment: trac_13646_fix_mip.patch

CC: @vbraun @ypfmde @dimpase @ptrrsn

Component: linear programming

Author: Nathann Cohen, Volker Braun

Reviewer: Dmitrii Pasechnik

Merged: sage-5.5.beta1

Issue created by migration from https://trac.sagemath.org/ticket/13646

[nathanncohen]

comment:3

Here it is ! There was some bad side effect with the previous patch :-)

Nathann

[nathanncohen]

comment:4

RHAAAAAAAAAAAAAAAAA

[vbraun]

comment:5

Don't just raise the error on some hand-picked "wrong" values. Add an else: branch to the last if-statement in __init__ as a catch-all.

[nathanncohen]

comment:6

Actually the patch works. My version of Sage doesn't pass all tests, but it seems to come from somewhere else..

Don't just raise the error on some hand-picked "wrong" values. Add an else: branch to the last if-statement in __init__ as a catch-all.

Well, True and False are what is returned when the left side is an integer, and only then. Plus I have no idea how to solve this bug in any different way O_o

I do not get what you mean by your Add an else: branch to the last if-statement in `__init__` as a catch-all. either O_o

Nathann

[vbraun]

Changed author from Nathann Cohen to Nathann Cohen, Volker Braun

[vbraun]

comment:7

I've folded your changes into my patch.

There are two things to do. 1) the chained inequalities need a parent as well, analogous to linear functions. 2) the base ring of the linear functions needs to match the capabilities of the backend. I've hardcoded the base ring as RDF for now. But somebody needs to add a method to the backends to query their supported base ring so we can plug that into the linear functions parent.

But I think those can be dealt with separately, and I'll leave them as an exercise for you :-) The biggest usability wart is patched, at least.

[dimpase]

comment:9

Replying to @vbraun:

I've folded your changes into my patch.

There are two things to do. 1) the chained inequalities need a parent as well, analogous to linear functions. 2) the base ring of the linear functions needs to match the capabilities of the backend. I've hardcoded the base ring as RDF for now. But somebody needs to add a method to the backends to query their supported base ring so we can plug that into the linear functions parent.

But I think those can be dealt with separately, and I'll leave them as an exercise for you :-) The biggest usability wart is patched, at least.

I don't think I understand the logic of the design to be able to do the exercise. Why does the base ring need to be hardcoded to anything? Ideally, I would like to see this coordinated with #12533.

[vbraun]

comment:10

The base ring should not be hardcoded. But you can't hook into Sage's coercion system if you don't have an idea of what your base ring is. So until somebody fixes the backends to report whatever the base ring is, it'll be RDF.

[nathanncohen]

comment:11

Not to mention that having RDF as a BaseRing would mean that a call to p.show() (that currently displays the LP's constraints) would result in ugly 1.0000000 everywhere instead of 1. No way -- I prefer having neat 1.0 than being able to write 5 <=variable.

QQ would be much better... Because of #12533 of course, and it would also be less destructive to everything else.

By the way, why did you replace Sum by p.sum ? I won't begin to say that it is not a backward compatible change -- I'm usually the least to worry about this. But given that it would completely break something like years of code I have, I would at least like to know why :-P

Nathann

[vbraun]

comment:17

I've also removed the deep copy, now naive addition is only about 2x slower than using sum:

sage: P = MixedIntegerLinearProgram()
sage: x = P.new_variable(binary=True)

sage: %prun for i in [0..290]: c = sum(x[j]*(j-i) for j in [0..290])
         99278 function calls in 1.681 seconds

sage: %prun for i in [0..290]: c = P.sum(x[j]*(j-i) for j in [0..290])
         98405 function calls in 0.928 seconds

[vbraun]

Changed dependencies from #12533 to none

[nathanncohen]

comment:19

Volker,

Before anything, please consider that your patches DO break a lot of code I (and some others probably that I do not know) have been using for a while, and that I have a very hard time keeping from shouting by myself in my office when I see you do that without caring about those consequences in any way.

Now that this is said, your patch has good aspects too. So let's talk about it, without forgetting this important detail.

Returning None as the value of a sum is not cool,

Yeah.... Let's not make a mess of a code just because of that.

stuff will almost certainly break if you return nothing and not the neutral element in the module.

Well, please consider that it just does not. All the code that you touch has been running for a while now, it wasn't even a module, and there was nothing wrong with it, except this 4 <= variable thing. So NO, having it return None sometimes is not a problem by itself. I don't have to explain why as you just have to accept that it does not. And I swear this code has been used.

None is also the value of undefined variables (e.g. typos), this is rather dangerous.

In this case True/False are the value of undefined linear expressions. No problem with None. You shouldn't say such things without knowing how this code is used.

This is why I switched sum to a method,

Yeah, and it destroys years of source code I have. As I said, I don't mind much if the changes are good, but it would be very impolite of you to not inquire about it before sending that patch.

so that it can return the correct neutral element. As a side effect it saves you from manually importing Sum and it makes it discoverable by tab completion.

I'll put in a deprecation for Sum.

Do we agree if we say that this change with Sum has NOTHING TO DO with the change of base ring ? As you hardcode the basering once, you could hardcode it twice (once in MILP, another in Sum), and anyway because we are dealing with RDF and nothing more complicated this Sum may all the same return int(0) when it is empty for all we care ?
It could even return MixedIntegerLinearProgram.base_ring()[1] for all we care ?

If these changes are disjoint, please say so. I would be glad to have this patch only fix the bug reported, and create another ticket for the change from Sum to p.sum. This latter part is more problematic, I mentionned many times that it destroyed years of code, but it seems to be a nice change anyway so why not, after all ?
But it would be nice to do this in a different ticket. If only to be able to actually see what this patch does with respect to the bug reported :-P

Thank you for your help in solving this thing though. I had no idea how to do that :-)

Nathann

[vbraun]

comment:20

I found a lot of places in the graphs stuff where Sum(...) + Sum(...) occurs. As soon as one of the sums returns None this will raise a TypeError. And the problem is precisely that it can't return MixedIntegerLinearProgram.base_ring() because that requires an instance of MixedIntegerLinearProgram. Right now the Sum is just deprecated, so you have at least a year to replace Sum() -> p.sum(). Which is a pretty simple search&replace. No code will break with this patch, you only get a deprecation warning the first time that you use Sum.

We will remove the hardcoded RDF in #13650, so its just a matter of time until its gone. Its not an option to hardcode RDF in Sum in the long run.

[nathanncohen]

comment:21

I found a lot of places in the graphs stuff where Sum(...) + Sum(...) occurs. As soon as one of the sums returns None this will raise a TypeError.

And if it never did, it may be because there is mathematical reason for that, or did you make sure of the opposite ?

And the problem is precisely that it can't return MixedIntegerLinearProgram.base_ring() because that requires an instance of MixedIntegerLinearProgram.

How come you ignored my question about returning int(0) ?

Right now the Sum is just deprecated, so you have at least a year to replace Sum() -> p.sum(). Which is a pretty simple search&replace. No code will break with this patch, you only get a deprecation warning the first time that you use Sum.

Nice.

We will remove the hardcoded RDF in #13650, so its just a matter of time until its gone. Its not an option to hardcode RDF in Sum in the long run.

It has been an option to not have a base ring at all for a very long while now.

Nathann

[vbraun]

comment:22

Having Sum() return int(0) is also tricky, think about

p.add_constraint( Sum(...) <= 123 )

Now this breaks because int(0) <= 123 evaluates to True. Since neither the left nor the right hand side is of type LinearFunction, there is no type information to construct a LinearConstraint.

It wasn't really ever an option to not play nice with the coercion system, you just let users again and again fall into the same trap ;-) But since now there is a QQ in addition to RDF backends its even more pressing to fix this up, I think.

[dimpase]

comment:23

Replying to @nathanncohen:

I found a lot of places in the graphs stuff where Sum(...) + Sum(...) occurs. As soon as one of the sums returns None this will raise a TypeError.

And if it never did, it may be because there is mathematical reason for that, or did you make sure of the opposite ?

One surely can code in a very dangerous style, but this does not mean that it should be forced upon the many Sage users.
E.g. #12091 (largely a duplicate of the current ticket) is a very good example (actually, #12091 seems to be fixed by the Volker's patch---at least the 1st example in the ticket description is fixed!) of pitfalls the current LP code is creating.

For one, I would kill for Sum() returning what it should, and not None.

It's sad it might break some private code, but it's a fact of life. Sage cannot always maintain the backward compatibility, after all. E.g. a move to Python 3 will break stuff for a lot of people. Please show us a typical fragment broken by Volker's patch, and we will see the best workaround. (Well, it could be that all it needs is a private definition of Sum(), can't tell without looking.)

We will remove the hardcoded RDF in #13650, so its just a matter of time until its gone. Its not an option to hardcode RDF in Sum in the long run.

It has been an option to not have a base ring at all for a very long while now.

Sure, but it was a bad design decision not to have one.

[dimpase]

comment:24

with #13650, looks set to go. Tested with various (optional) backends, too.

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:26

before I forgot: with Gurobi version 5.0, its LP output format has changed a bit. It numbers the constraints now:

    Constraints:
      R0: x_0 + x_1 <= 10.0
      R2: x_0 <= 4.0

rather than

    Constraints:
      x_0 + x_1 <= 10.0
      x_0 <= 4.0

Nathann, do we want a doctest patch for this? (Well, I imagine that on older systems, or for license-related reasons, people still use version 4).

[nathanncohen]

comment:27

Honestly, I would have liked to review that patch, but today I turn my computer on and I see it reviewed. There's nothing I can do about that. Concerning doctests : I do not remember that Gurobi "changed" at some point with respect to labels, but maybe you are right. There may be a way in Gurobi to check which version is used, but to me it is much more trouble than is necessary. Well, that's up to you ! It is also extremely difficult to play with differents versions of Gurobi at the same time to test those things.

Have fun with the code, I'll be out of it for the next days... My days are stolen by people around me this time, and I need to do what I have to during the short time that I have left.

Nathann

[dimpase]

comment:28

Replying to @nathanncohen:

Honestly, I would have liked to review that patch, but today I turn my computer on and I see it reviewed.

?אם אין אני לי, מי לי? וכשאני לעצמי, מה אני? ואם לא עכשיו, אימתי ;-)

[jdemeyer]

comment:29

The patch needs a proper commit message.

[vbraun]

Attachment: trac_13646_fix_mip.patch.gz

Updated patch

[vbraun]

comment:30

Oops, fixed. I was going to suggest that the patchbot should check this but it does already ;-)

[dimpase]

comment:31

Replying to @vbraun:

Oops, fixed. I was going to suggest that the patchbot should check this but it does already ;-)

Yeah, AI in action! Bots are taking over Sage development!

[jdemeyer]

Merged: sage-5.5.beta1

[jdemeyer]

Changed reviewer from Dima Pasechnik to Dmitrii Pasechnik