Opened 9 years ago

Closed 9 years ago

#12309 closed defect (fixed)

GLPK crashes or hangs on certain inputs

Reported by: john_perry Owned by: ncohen
Priority: major Milestone: sage-5.0
Component: linear programming Keywords:
Cc: malb, ncohen Merged in: sage-5.0.beta2
Authors: John Perry Reviewers: Nathann Cohen
Report Upstream: Reported upstream. Developers deny it's a bug. Work issues:
Branch: Commit:
Dependencies: #10785 Stopgaps:

Description (last modified by john_perry)

The attached sage script (inhomogeneous_bug_test.py) creates a linear system that

  • crashes Sage if the variables are continuous, and
  • hangs Sage if the variables are integer.

Nathann determined that this was a bug with GLPK, the underlying solver. I have attached a C++ program (glpk_bug.cpp) that reproduces the bug directly via the GLPK library, and passed it on to the developers.

I can't resist the temptation to say that the developers don't consider this a bug, but a feature; see

This thread on the bug-glpk mailing list archive

and

GLPK/Known Issues

where they call this behavior essentially innate. The workaround is to set upper bounds.

Sage's documentation should provide this information to the user, and suggest the workaround. We should also try trapping the exception, and notifying the user.

Apply:

trac_12309.patch

Attachments (3)

inhomogeneous_bug_test.py (2.6 KB) - added by john_perry 9 years ago.
glpk_bug.cpp (7.7 KB) - added by john_perry 9 years ago.
trac_12309.patch (7.1 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (20)

Changed 9 years ago by john_perry

Changed 9 years ago by john_perry

comment:1 Changed 9 years ago by john_perry

If no one is in any particular rush, I'll add a patch in a few days. I'd also like the patch to allow the user to decide that (s)he wants to use the glp_simplex solver rather than the glp_intopt solver, since glp_simplex does not crash on these inputs.

comment:2 Changed 9 years ago by john_perry

  • Description modified (diff)
  • Status changed from new to needs_review

The patch I am about to upload (not the one I just finished uploading) adds the preprocessing option, an exception for preprocessing failure, a sig_str() and sig_off() pair that catch the crash on the infeasible system in the example, documentation of the new solver option, and a doctest that raises the new exception. The doctest passes on my machine.

In short, it does everything the ticket asked for. Needs review!

comment:3 Changed 9 years ago by john_perry

  • Dependencies set to #10785

comment:4 Changed 9 years ago by john_perry

I just discovered a bug in the copy function: I did not copy the preprocessing option. For that matter, ticket #10785 did not copy the tm_lim option that it introduced. The new patch takes care of those.

comment:5 follow-up: Changed 9 years ago by ncohen

Hellooooooo !!

It seems weird that the loglevel has to be stored in *BOTH* iocp and smcp O_o Isn't just one of them necessary ? And you also thought of copying the self.preprocessing variable but it is not the only one that can be set with GLPK. The "timelimit" option is also exposed, and we probably can do better than to store everything twice and redefine it in the new copy. Isn't there a "GLPK way" to copy the content of a scmp object ? It would be nice to let GLPK do the job, or we would have to create a new variable each time we expose a new parameter O_o

By the way, I reinstalled Sage and tested the CBC patch, but of course it still returns this "gzopen function non found" error message I told you some time ago... And as the fix I had found does not work on your computer we are not done yet :-D

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 9 years ago by john_perry

Replying to ncohen:

It seems weird that the loglevel has to be stored in *BOTH* iocp and smcp O_o Isn't just one of them necessary ?

glp_simplex doesn't take iocp parameters.

Isn't there a "GLPK way" to copy the content of a scmp object ? It would be nice to let GLPK do the job, or we would have to create a new variable each time we expose a new parameter

Even if true, and it probably is, that would still be overkill, given our current setup. The smcp and iocp structures are created in __cinit__ regardless of whether we're copying or creating. If the copy function were then to invoke GLPK's copy constructor (or whatever) then we would be creating the same thing twice, merely to avoid setting two parameters directly?

comment:7 in reply to: ↑ 6 ; follow-ups: Changed 9 years ago by ncohen

glp_simplex doesn't take iocp parameters.

Right right, so you need to update its log level too ! Sorry about that.

Even if true, and it probably is, that would still be overkill

Granted, granted. So I only have two remarks on your patch :

  • First, I guess that self.scmp behaves like self.iocp and should also be deallocated in dealloc
  • Could you add a doctest that shows the signal returned by your code when a bad lp is solved without the preprocessing flag, and how it is solved afterwards ? The shortest bad example I was able to produce from you .py file is this one :
    lp = MixedIntegerLinearProgram(solver="GLPK")
    lp.add_constraint( lp[1] +lp[2] -2.0 *lp[3] , max =-1.0)
    lp.add_constraint( lp[0] -4.0/3 *lp[1] +1.0/3 *lp[2] , max =-1.0/3) # <-- succeeds up to here w/last line                                                                                                                                                                        
    lp.add_constraint( lp[0] +0.5 *lp[1] -0.5 *lp[2] +0.25 *lp[3] , max =-0.25) # <--- fails here w/last line                                                                                                                                                                        
    lp.add_constraint( lp[0] +4.0 *lp[1] -lp[2] +lp[3] , max =-1.0) # <-- last line                                                                                                                                                                                                  
    lp.solve()
    

I also believe the documentation you added about the preprocessing flag is worth being in a .. WARNING:: environment. This way it'll appear in red in the HTML documentation, and should attract the attention of somebody having some troubles with GLPK. That's up to you :-)

Sorry if I am being a little slow, there are several nasty patches needing attention at the same time (not to mention the awful CBC one) and "free time" is a long-forgotten dream these days O_o

Nathann

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

Replying to ncohen:

  • First, I guess that self.scmp behaves like self.iocp and should also be deallocated in dealloc

Duh. :-)

  • Could you add a doctest that shows the signal returned by your code when a bad lp is solved without the preprocessing flag, and how it is solved afterwards ?

Wow, thanks! I didn't think I could get one that small easily. I will replace the doctest I added with that one instead.

I also believe the documentation you added about the preprocessing flag is worth being in a .. WARNING:: environment. This way it'll appear in red in the HTML documentation, and should attract the attention of somebody having some troubles with GLPK. That's up to you :-)

That's perfect; I wasn't really aware of it.

Sorry if I am being a little slow, there are several nasty patches needing attention at the same time (not to mention the awful CBC one) and "free time" is a long-forgotten dream these days O_o

I know what you mean, and I'm not complaining. If a couple of weeks passed, I'd more likely post a request at sage-devel anyway.

Thanks a lot!

comment:9 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by john_perry

Replying to ncohen:

  • Could you add a doctest that shows the signal returned by your code when a bad lp is solved without the preprocessing flag, and how it is solved afterwards ?

Apparently not, by the way. If I try to solve without setting the parameter, the doctest fails because an exception is raised.

I'm looking at the manual to see if I can find a way around this.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 9 years ago by ncohen

Apparently not, by the way. If I try to solve without setting the parameter, the doctest fails because an exception is raised.

Oh, but you can "test" exceptions too ! Look at a file like mip.pyx and look for "traceback"

Nathann

comment:11 in reply to: ↑ 10 Changed 9 years ago by john_perry

Replying to ncohen:

Oh, but you can "test" exceptions too ! Look at a file like mip.pyx and look for "traceback"

Hey, you're awake :-) Thanks, that worked. New patch in a sec.

comment:12 Changed 9 years ago by john_perry

Wait. Is the warning supposed to be indented inside the ..WARNING:: ?

comment:13 Changed 9 years ago by john_perry

Oops. Yes, it is supposed to be indented. Hopefully, that's fixed now.

Changed 9 years ago by ncohen

comment:14 follow-up: Changed 9 years ago by ncohen

  • Authors set to John Perry
  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Helloooooo !!

Ahem. Your patch was missing a space between ".." and "warning", and because of that the documentation was not properly built. I could not bring myself to set the ticket back to "needs work" so I changed it myself and reuploaded your own patch after adding the space ^^;

Good to go ! :-)

comment:15 in reply to: ↑ 14 ; follow-up: Changed 9 years ago by john_perry

Replying to ncohen:

Ahem. Your patch was missing a space between ".." and "warning", and because of that the documentation was not properly built. I could not bring myself to set the ticket back to "needs work" so I changed it myself and reuploaded your own patch after adding the space ^^;

LOL

How do I test that the documentation is built properly? Run it in the notebook?

comment:16 in reply to: ↑ 15 Changed 9 years ago by ncohen

Yoooooooooooo !!

How do I test that the documentation is built properly? Run it in the notebook?

nop ! You just have to run "sage -docbuild reference html" The first run may (it depends on the releases) take some times, but you can rebuild it in a few seconds afterwards when you update the files.

It will tell you where the html files are located on your computer. And I guess it will also update the one used by the notebook though I really never use it ^^;

Nathann

comment:17 Changed 9 years ago by jdemeyer

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