Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#13646 closed defect (fixed)

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

Reported by: ncohen Owned by: ncohen
Priority: major Milestone: sage-5.5
Component: linear programming Keywords:
Cc: vbraun, pmueller, dimpase, ptrrsn_1 Merged in: sage-5.5.beta1
Authors: Nathann Cohen, Volker Braun Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by vbraun)

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

Attachments (1)

trac_13646_fix_mip.patch (82.1 KB) - added by vbraun 7 years ago.
Updated patch

Download all attachments as: .zip

Change History (34)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:3 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Nathann

comment:4 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

RHAAAAAAAAAAAAAAAAA

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

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.

comment:6 in reply to: ↑ 5 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

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

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

  • Authors changed from Nathann Cohen to Nathann Cohen, Volker Braun
  • Cc dimpase added
  • Description modified (diff)

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.

comment:8 Changed 7 years ago by vbraun

  • Description modified (diff)

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

  • Cc ptrrsn_1 added
  • Status changed from needs_review to needs_info

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.

comment:10 Changed 7 years ago by vbraun

  • Status changed from needs_info to needs_review

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.

comment:11 Changed 7 years ago by ncohen

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

comment:12 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:13 Changed 7 years ago by ncohen

  • Dependencies set to #12533

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

  • Status changed from needs_info to needs_review

The output is fine, it prints 1.0 in p.show(). Did you actually try it?

Also, right now the coefficients aren't converted into the base ring unless the coercion framework requires it. This is something that should be fixed as well, so coefficients always live in the respective base ring. But thats another thing for later when the backends report their base ring.

With a stand-alone Sum function you can't do the empty sum - what would be its parent?

comment:15 in reply to: ↑ 14 Changed 7 years ago by ncohen

The output is fine, it prints 1.0 in p.show(). Did you actually try it?

I did not. I thought that it was one of the things you were leaving for later, while you indeed say the opposite in your message. Hadn't noticed that part.

Also, right now the coefficients aren't converted into the base ring unless the coercion framework requires it. This is something that should be fixed as well, so coefficients always live in the respective base ring. But thats another thing for later when the backends report their base ring.

With a stand-alone Sum function you can't do the empty sum - what would be its parent?

It used to return None, and I lived fine with it.

Could you please answer my question about sum to p.sum ?

Nathann

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

Returning None as the value of a sum is not cool, stuff will almost certainly break if you return nothing and not the neutral element in the module. None is also the value of undefined variables (e.g. typos), this is rather dangerous. This is why I switched sum to a method, 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.

comment:17 Changed 7 years ago by vbraun

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

comment:18 Changed 7 years ago by vbraun

  • Dependencies #12533 deleted

comment:19 in reply to: ↑ 16 Changed 7 years ago by ncohen

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

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

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.

comment:21 in reply to: ↑ 20 ; follow-up: Changed 7 years ago by ncohen

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

comment:22 Changed 7 years ago by vbraun

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.

comment:23 in reply to: ↑ 21 Changed 7 years ago by dimpase

Replying to ncohen:

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.

Last edited 7 years ago by dimpase (previous) (diff)

comment:24 Changed 7 years ago by dimpase

  • Status changed from needs_review to positive_review

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

comment:25 Changed 7 years ago by dimpase

  • Reviewers set to Dima Pasechnik

comment:26 Changed 7 years ago by dimpase

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

comment:27 follow-up: Changed 7 years ago by ncohen

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

comment:28 in reply to: ↑ 27 Changed 7 years ago by dimpase

Replying to ncohen:

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

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

comment:29 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The patch needs a proper commit message.

Changed 7 years ago by vbraun

Updated patch

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

  • Status changed from needs_work to positive_review

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

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

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!

comment:32 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.5.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:33 Changed 7 years ago by jdemeyer

  • Reviewers changed from Dima Pasechnik to Dmitrii Pasechnik
Note: See TracTickets for help on using tickets.