#12220 closed enhancement (fixed)
Updated CBC spkg
Reported by: | ncohen | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | packages: optional | Keywords: | sd35.5, Cernay2012 |
Cc: | malb, john_perry | Merged in: | sage-5.0.beta13 |
Authors: | John Perry, Nathann Cohen | Reviewers: | John Perry, Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Hello everybody !!!
Michael Walter reported a bug that could happen with the current CBC package. This spkg used to contain several files to enable the use of the CPLEX solver in old versions of Sage, stuff which had remained there so that the package would stay compatible with those old versions of Sage.
It has been a while, though.
It has been a while, and besides, this stuff actually created problems when somebody installed cplex before cbc : the cbc spkg tried to compile the CPLEX stuff even on new versions of Sage, and Sage actually did not like that :-)
The new spkg is available there, and the problem mentionned above is actually solved by removing some files and several lines in the former spkg-install.
While I was at it, I updated the source from 2.3 to 2.7.5, which is worth doing already.
Here it is : http://www.steinertriples.fr/ncohen/cbc-2.7.5.spkg
(there is also a small patch removing a few characters from module_list.py)
Nathann
Apply:
Attachments (12)
Change History (107)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:3 follow-up: ↓ 4 Changed 8 years ago by
comment:4 in reply to: ↑ 3 Changed 8 years ago by
What needs work? (I haven't look at it yet, sorry if it's obvious.)
Also, are we going to change in this ticket from OsiCbc? to plain Cbc?
Precisely. I wanted to avoid that, but the new version of Cbc creates stupid (undocumented) problems... I have been struggling with this for hours already and I am tired of trying to guess which kind of options would make Cbc compile a correct binary.
I end up trying to find out how to directly use Cbc without Osi, and it's not that clearer for a while. So instead of the "new spkg + 2 lines patch" formula, it will probably be "new spkg with huge patch". Sick of this. Not to mention it will not be backward compatible -_-
Nathann
Changed 8 years ago by
comment:5 Changed 8 years ago by
I compiled a fresh alpha, installed cbc-2.3.2, then did the sage -f cbc-2.7.5.spkg
, then tried to build. I get:
Error compiling Cython file: ... c_CoinPackedMatrix * getMatrixByRow() CbcModel * CbcModel(OsiClpSolverInterface solver) ^ ------------------------------------------------------------ sage/numerical/backends/coin_backend.pxd:93:29: 'OsiClpSolverInterface' is not a type identifier
It may be my fault, but if so, I don't understand why. For that matter, I don't know why it's complaining about this.
comment:6 follow-up: ↓ 7 Changed 8 years ago by
I got somewhere. I can get past the compilation stage if I rearrange the declarations so that OsiClpSolverInterface
is declared before CbcModel
, and also OsiSolverInterface
is declared before OsiClpSolverInterface
. (I still don't understand why; that seems bizarre.)
However, linking then fails. The last few lines of output are:
g++ -L/Applications/sage_bugs/sage-4.8.alpha0/local/lib -bundle -undefined dynamic_lookup build/temp.macosx-10.6-i386-2.6/sage/numerical/backends/coin_backend.o -L/Applications/sage_bugs/sage-4.8.alpha0/local/lib -lcsage -lcsage -lstdc++ -lCbc -lCgl -lCbcSolver -lClp -lCoinUtils -lOsiClp -lOsi -lrt -lstdc++ -lntl -o build/lib.macosx-10.6-i386-2.6/sage/numerical/backends/coin_backend.so ld: library not found for -lrt collect2: ld returned 1 exit status error: command 'g++' failed with exit status 1 sage: There was an error installing modified sage library code.
There is, indeed, no librt
in the directory specified. Is that supposed to be linked?
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 8 years ago by
There is, indeed, no
librt
in the directory specified. Is that supposed to be linked?
I must have spent 2 or 3 hours finding out that this solved a bug on my own machine. Without this librt flag, any call to the library immediately fails -_- I thought it was safe to add it, but if it fails on your computer then it would not do as a Sage spkg.
Well... Then remove it and try again, perhaps it will work on your computer. On mine, it produced errors like "can not find get_clock" or something like that.
Looks like we are not there yet... O_o
Nathann
comment:8 in reply to: ↑ 7 Changed 8 years ago by
Replying to ncohen:
There is, indeed, no
librt
in the directory specified. Is that supposed to be linked?I must have spent 2 or 3 hours finding out that this solved a bug on my own machine.
8-O
Without this librt flag, any call to the library immediately fails -_-
8-O 8-O
Well... Then remove it and try again, perhaps it will work on your computer. On mine, it produced errors like "can not find get_clock" or something like that.
For once, I figured out on my own what to remove it from (please tell me it's the file, module_list.py
). It compiled fine, and I was able to run one of my favorite LPs:
sage: lp = MixedIntegerLinearProgram(solver='Coin') sage: lp.add_constraint(lp[0]-lp[1],min=1) sage: lp.add_constraint(2*lp[0]-3*lp[1],min=1) sage: lp.add_constraint(lp[0],min=1) sage: lp.add_constraint(lp[1],min=1) sage: lp.solve() 0.0 sage: lp.get_values([lp[0],lp[1]]) [2.0, 1.0]
It's a regular, happy camper. I haven't tested it much, but so far it seems to be doing just fine.
Out of curiosity, are those ctypedef
s supposed to go in a certain order? Cython documentation doesn't seem clear on this.
comment:9 Changed 8 years ago by
By the way, copying works, too :-) :-) :-)
I copied an LP 20 times with no trouble.
(And I had just gotten my own simplex working in my program. The irony... the irony...)
comment:10 follow-up: ↓ 11 Changed 8 years ago by
Nice ! And it was the modules_list file indeed ! :-)
The problem is that it does not work without this on my computer. Anyway, once you get it running we should be at the same level : I do not remember what still failed when I gave up, but if I gave up it should be a nasty thing. I remember I was able to solve LP so the problem lied somewhere else. You can give sage -t numerical/
a try to see where the problem lies
:-)
Nathann
comment:11 in reply to: ↑ 10 Changed 8 years ago by
Replying to ncohen:
I do not remember what still failed when I gave up, but if I gave up it should be a nasty thing. I remember I was able to solve LP so the problem lied somewhere else. You can give
sage -t numerical/
a try to see where the problem lies
:-)
If I run sage -t sage/numerical/backends/coin_backend.pyx
I only get one failure: the one about setting the number of threads.
If I run sage -t sage/numerical/
I get some failures in mip.pyx
that I've seen before installing this one; they're related to other tickets, not Coin. (This is a fresh alpha0 install, not alpha4 or later.) I can be more specific if you want.
What is this number of threads business? Is it related to parallelism?
[PS I meant to add this yesterday; apparently I hit the "preview" button, instead.]
comment:12 Changed 8 years ago by
Some very bad news.
It's true that copying a program many times doesn't generate the same memory corruption that it did before. Unfortunately, that seems to be because it isn't copying anything. Worse, we get an "Unhandled SIGSEV" if we copy & try to add constraints.
I'll try to look at it...
comment:13 Changed 8 years ago by
Hello !
Yep, the number of threads is the number of paralell process that coin uses to solve problem. It is really nice to have it use all the processors available, but there *IS* to be some way to set it through this new class. The other problem is the verbosity level. It does not appear in the doctests because Coin is directly displaying information through stderr (I guess), so Python does not mean anything. The problem is that if you type : graphs.PetersenGraph?().dominating_set() you will get some informations from Coin you should not see unless you explicitely ask for them. I think this is the only problem left with the package, considering we can also solve this nasty compiling problem :-/
(The one I solve by adding "librt" to the flags, the one you solve by removing it :-p
)
Nathann
comment:14 Changed 8 years ago by
I found the problem with verbosity. setLogLevel()
won't do squat with the issues we're seeing, because the messages we're looking at don't go through the interface's messageHandler()
; instead, they are piped directly to std::cout
. See line 7893 of OsiClpSolverInterface.cpp
, and a few other lines as well.
This looks like an upstream bug. I will report it. With any luck, I'll get some feedback. However, unless we can somehow change std::cout to /dev/null or some such, we're probably stuck with this for the indefinite future.
Next up: threads.
comment:15 Changed 8 years ago by
I think I've found threads.
In class OsiClpSolverInterface
, there's a method,
ClpSimplex * getModelPtr();
It turns out that ClpSimplex
inherits from ClpModel
, wherein we find
void setNumberThreads(int value)
I am not sure it actually does anything with the threads, since the method is commented with
/// Number of threads (not very operational)
but perhaps its descendant ClpSimplex
does something with it.
To activate this, I am adding the following lines to OsiSolverInterface.pxd
:
cdef extern from "../../local/include/coin/ClpModel.hpp": cdef cppclass ClpModel: void setNumberThreads(int value) int numberThreads() cdef extern from "../../local/include/coin/ClpSimplex.hpp": cdef cppclass ClpSimplex(ClpModel): pass cdef extern from "../../local/include/coin/OsiClpSolverInterface.hpp": cdef cppclass OsiClpSolverInterface(OsiSolverInterface): ... ClpSimplex * getModelPtr() ...
and in __cinit__()
for OsiClpSolverInterface.pyx
now sets it up as:
#self.si = new CoinModel(NULL) cdef OsiClpSolverInterface * si_model = self.si cdef ClpSimplex * model = si_model.getModelPtr() import multiprocessing model.setNumberThreads(multiprocessing.cpu_count())
As far as I can tell, this seems to work: it compiles & links, and Coin seems to be working properly; that is, I'm not encountering any errors. I don't know how to test it, though; any advice?
Also, does this look sensible? If so, I'll upload a new patch containing all the changes I've made so far.
comment:16 follow-up: ↓ 18 Changed 8 years ago by
Well, no, defining a method to set the number of thread in a class representing LINEAR programs (and not integer ones) is not very sensible. But that's hardly your fault O_o
Well, the best way to check that it works is to solve a hard integer problem. I advise you to give this a try :
sage: graphs.Grid2dGraph(10,10).minor(graphs.CompleteGraph(5))
But do not expect it to return an answer :-P
If the flag works it should appear in "htop", or any software you use to know the cpu load.
And thank you very much for your work on this ticket :-)
Nathann
comment:17 Changed 8 years ago by
Upstream replies on the verbosity:
That code is in OsiClpSolverInterface::branchAndBound
That was never meant to be used in a production environment - Cbc's branch and bound using OsiClp? can be orders of magnitude faster.
It would not take much to rewrite to send to messageHandler, but what are your needs which need to use this particular piece of code?
John Forrest
comment:18 in reply to: ↑ 16 Changed 8 years ago by
Replying to ncohen:
sage: graphs.Grid2dGraph(10,10).minor(graphs.CompleteGraph(5))But do not expect it to return an answer
:-P
Only 50% CPU usage. Bummer.
As I mentioned in email to you, I'm going to try adapting Cbc according to John Forrest's second email (not copied here). :-/ We'll see how this turns out...
comment:19 Changed 8 years ago by
BTW, it looks (from example driver3.cpp
) that I won't have to complete rewrite the whole thing.
comment:20 Changed 8 years ago by
Quick update.
Right now I can set up & copy a coin solver using CBC. I can create rows & variables. I can set threads. I might be able to set verbosity, but I'm not yet sure. That's because...
...the only thing I can't do right now is, uh, well, actually solve an LP. Their example is a little funny there, though, so that doesn't surprise me. I'll have to examine their code a little more carefully, and figure out why on earth they do certain things.
Still working...
comment:21 Changed 8 years ago by
Solving is working. Ironically, it was probably working when I said it wasn't; I just didn't realize that I needed to change to code to look for signals like isAbandoned
from the model and not from the interface.
I should have a patch candidate Real Soon Now (TM). As in, sometime tomorrow.
comment:22 Changed 8 years ago by
I'm getting there. I haven't run doctests yet, and in particular, I don't like having to recopy the cbc model every time I try to solve. I'm reasonably sure that's inefficient, though I might be wrong. I want to try another avenue before I go into doctests.
comment:23 Changed 8 years ago by
Sorry -- I mean, "reinitialize a cbc model", not "recopy the cbc model".
The underlying solver remains exactly the same, and that's the thing that contains the constraints, objective function, etc. It just doesn't contain the solution.
The model contains the solution, but not (apparently) a useful solver after we solve it.
I'm about to try something that will involve changing the solver.
comment:24 Changed 8 years ago by
By the way, if I want to test parallelism, how do I tell graphs to use the Coin solver? I am not sure that, when I tested it earlier, it was using Coin.
comment:25 Changed 8 years ago by
- Status changed from needs_work to needs_info
I've inquired w/Cbc list about whether it's possible to retain the model after solving. If, as I suspect, it is not, then the situation I'm envisioning now is the following: the CoinBackend
will have the following data members: solution
, an array of doubles initialized to NULL
; obj_value
, the objective value of the solution; log_level
, the amount of verbosity desired. If the user requests a solution or the objective value, an exception is raised if solution == NULL
; otherwise, the data requested is given. Whenever the user modifies the LP in anyway way (adds columns, rows, etc.), solution
will be set to NULL
, since the old solution is no longer valid.
This setup makes a lot of sense to me, but do you foresee anything going wrong with it?
comment:26 follow-up: ↓ 27 Changed 8 years ago by
Hello !
When you talk about "the model", do you mean that you have to copy all the constraints and variables again if you ever want to 1) solve a LP 2) add a constraint 3) solve it again ?
Nathann
comment:27 in reply to: ↑ 26 Changed 8 years ago by
Replying to ncohen:
When you talk about "the model", do you mean that you have to copy all the constraints and variables again if you ever want to 1) solve a LP 2) add a constraint 3) solve it again ?
Here's a rough sketch of what works.
- let si = new OsiClpSolverInterface?()
- while not done:
- add constraints, variables, whatnot to si
- let model = new CbcModel?(si)
- model.branchAndCut()
- extract solutions from model.si, evaluate done
Step 2b clones si, so I think the answer to your question is, yes. I find this deeply unsatisfying myself, but if I try to move that step outside the loop and modify Cbc's model after solving, Sage gives a SIGSEV
.
The only alternative I know of right now is to use OsiClpSolverInterface
alone, but (a) the developers have told me repeatedly that its branchAndBound
() is orders of magnitude slower than CbcModel
, and (b) this is the method that ignores the setLogLevel
method.
As I say, I've inquired at their list:
http://list.coin-or.org/pipermail/cbc/2012-January/000751.html
but as of this moment, I don't yet have an answer.
Actually, all this discussion reminds me of something. CbcModel
has an assignSolver()
method whose parameter has type OsiSolverInterface * &
. Notice the pointer; the argument for the constructor I'm using has type OsiSolverInterface &
, which as I understand it necessarily creates a copy of the parameter. ` One reason I'm not using it now is that, when I was trying to, I was also having issues with Cython's quirks. I'll see if I can use that; looking at the code, it doesn't seem to clone the solver.
comment:28 follow-up: ↓ 30 Changed 8 years ago by
Got it.
To answer one of your previous posts, though, I am also a bit tired to try to patch above in Python what look like very bad design pattern in the library. I would feel much better raising an exception whenever the user wants to solve a LP that has been solved already, something saying "This is not possible with Coin" rather than add many arguments, copying them, all operations for which the user has no way to guess that they actually require a lot of (useless) computations... O_o
Nathann
comment:29 Changed 8 years ago by
By the way, this is more or less what happens already with Coin : I met this problem of not being able to add constraints then resolve the LP when adding to Sage the first lienar programs using constraint generation. Which is precisely that : solve, add a constraint, solve again, add a constraint, etc...
The function get_solver ( http://www.sagemath.org/doc/reference/sage/numerical/backends/generic_backend.html ) has a parameter named constraint_generation
, which is just there to have the method return the "best solver installed on the machine", except Coin if constraint generation is necessary. I hoped that perhaps by changing the backend this limitation would disappear, but well.... I do not want to say "you can use constraint generation with Coin" if it just amounts to copy many times the solver. It would just be bad code, nothing else.
Nathann
comment:30 in reply to: ↑ 28 Changed 8 years ago by
Replying to ncohen:
I would feel much better raising an exception whenever the user wants to solve a LP that has been solved already, something saying "This is not possible with Coin"...
The problem with that for me, of course, is that GLPK (or, at least, Sage's interface to it) segfaults on the problem I'm working on. Coin seems to solve my problems. :-)
comment:31 Changed 8 years ago by
Oh, but that is not necessarily a problem in this case. I mean, it would be necessary to hard-code the copy of the whole problem in low-level functions of the MILP class to make it work anyway, so the operations would still work by copying the MILP object just before solving it and it would not change the complexity, would it ?
But if you do that, you definitely know that you are copying the program and do not believe that you are just "adding a constraint" while what Sage does is actually much much longer.
Nathann
comment:32 Changed 8 years ago by
Update: assignSolver()
always segfaults when I pass it an OsiSolverInterface()
. I'll look through the examples to try & figure out why, but here's an interesting comment in the Coin source:
Note that CbcModel? clones solvers with abandon. Unless you have a deep understanding of the workings of CbcModel?, the only time you want to claim ownership [of a solver] is when you're about to delete the CbcModel? object but want the solver to continue to exist (as, for example, when branchAndBound has finished and you want to hang on to the answer).
That happens to be our situation.
comment:33 Changed 8 years ago by
Good news and bad news.
setModelOwnsSolver()
allows me to retain the solver interface afterCbcModel
finishes with it. I can get solutions, even add new constraints.- Unfortunately, if I do add a constraint after solving once,
CbcModel
doesn't seem capable of solving the new system. Even if I add a constraint that maintains feasibility, I get the message,
MIPSolverException: 'CBC : The problem or its dual has been proven infeasible!'
- There are no examples of using either
setModelOwnsSolver()
orassignSolver()
.
I'm guessing the designers never imagined that someone might want to add constraints to the system. I could be wrong, and hope I am. If they reply to my latest email, we'll know for sure.
As things stand now, we have two options: use either OsiClpSolverInterface
only with its verbosity and slow branchAndBound()
, or OsiClpSolverInterface
and CbcModel
with a fast branchAndBound()
but possibly slow solving with new constraints.
Right now, I'm favorable to CbcModel
, since that's what the Coin developers are pushing. Also, it takes care of the verbosity issue. Unfortunately, setting the number of threads in the model doesn't seem to help with multiprocessing, at least if the example you gave me is an indicator (assuming it's using Coin
, which I think it is, but I'm not 100% sure). Let me know if you think I should go with OsiClpSolverInterface
only, instead.
I'm going to start doctesting & fixing any bugs that pop up.
comment:34 Changed 8 years ago by
The only doctest errors remaining now
- those related to row, column, and problem names, which are not currently implemented in
CoinBackend
, and - an exception generated by a call to
write_lp
, which is not implemented.
In other words, these are things that have nothing to do with the code I have right now.
I can easily fix the first, either by implementing Coin's own name facility, or by implementing one of my own (in case std::string
gives me fits). As for the second, I don't know what to do. Thoughts?
comment:35 Changed 8 years ago by
- Status changed from needs_info to needs_review
I have a working patch. Names of the problem, rows, and columns are implemented in the Cython object as Python strings (the str
type). If C++'s std::string
is somehow accessible from Sage, I can implement them in the C++ object instead (i.e., the solver), but I'll need info on how to do that. I've left an inquiry at sage-devel.
One doctest doesn't pass: in mip.pyx
, the test of the write_lp()
method in line 685 raises a NotImplementedError
. Since this was never implemented with Coin, I don't consider it a deal breaker. I think I can fix it if you want; the OsiSolverInterface
provides a writeMps()
method that
Write[s] the problem in MPS format to the specified file.
So, I can implement that, too, if people insist, but I don't want to, and I'm not sure if the writeMps()
method does what the write_lp()
method is supposed to do. So, I won't do anything for now. :-P
Otherwise, all doctests pass. Please review.
comment:36 Changed 8 years ago by
- Description modified (diff)
Whoops -- forgot to change the instructions!
comment:37 Changed 8 years ago by
- Keywords sd35.5 added
comment:38 Changed 8 years ago by
Whoops -- I just looked at the patch, and I discovered that it didn't contain anything of substance! I had forgotten to qrefresh. Okay, the upcoming patch will finally have the data.
(Sorry if anyone looked & was confused...)
Changed 8 years ago by
comment:39 Changed 8 years ago by
- Description modified (diff)
(I wish there were a way to delete attachments!)
comment:40 follow-up: ↓ 41 Changed 8 years ago by
(let's not forget that)
Nathann
Changed 8 years ago by
comment:41 in reply to: ↑ 40 Changed 8 years ago by
Replying to ncohen:
(let's not forget that)
Nathann
What's this about? Is it the wrong ticket, or somethng I missed in the conversation?
comment:42 follow-up: ↓ 43 Changed 8 years ago by
NOnonono, it's just that this doctest fails when you have Cbc installed, because it does not support constraint generation and that the code is missing the corresponding flag to "avoid" Coin when it is installed. And I know I will never notice it again because I will remove coin from my machine as soon as this patch passes :-p
Nathann
comment:43 in reply to: ↑ 42 ; follow-up: ↓ 44 Changed 8 years ago by
Replying to ncohen:
And I know I will never notice it again because I will remove coin from my machine as soon as this patch passes
:-p
LOL Out of curiosity, did we resolve the issue with the spkg?
john
comment:44 in reply to: ↑ 43 ; follow-up: ↓ 45 Changed 8 years ago by
LOL Out of curiosity, did we resolve the issue with the spkg?
No, I still have not found how to compile the code without -lrt. Do you have any idea ?
Nathann
comment:45 in reply to: ↑ 44 ; follow-up: ↓ 46 Changed 8 years ago by
Replying to ncohen:
LOL Out of curiosity, did we resolve the issue with the spkg?
No, I still have not found how to compile the code without -lrt. Do you have any idea ?
How is the spkg built? When I build the Cbc libraries on either Linux or Mac, I don't have to specify this; I just configure and make. Are we not able to do that w/sage?
(Demonstrating my rank ignorance here...)
comment:46 in reply to: ↑ 45 ; follow-up: ↓ 47 Changed 8 years ago by
(Demonstrating my rank ignorance here...)
I would have been glad to ignore that myself, but that was before I had to deal with this CBC spkg.
Here's the problem : during the "./configure" step CBC detects (on linux) that the rt library is available and detects (on mac) that it is not in which case it uses a different code. The libraries are built. Then we build the coin_backend.pyx file in Sage, which calls the Coin library, hence this file has to be linked with the coin library. If (under linux) we do not also link coin_backend.pyx with rt then we get an exception saying that a function is missing in the lib. So we have to add a "rt" flag to module_list.py so that Sage links it. Yeah, but then it does not compile on Mac anymore because the library does not exist.
Ideally, we would like to force the ./configure script to ignore the rt library on linux but I have no idea how to do that.
Would you know how to get away with all that ? :-P
Nathann
comment:47 in reply to: ↑ 46 Changed 8 years ago by
Replying to ncohen:
Then we build the coin_backend.pyx file in Sage...
Okay, duh, that's the part I overlooked. :-D
comment:48 follow-up: ↓ 52 Changed 8 years ago by
- Summary changed from Updated CBC spkg to Updated CBC spkg (Cernay 2012)
Wouhouuuuuuuuuuuuuu !!!
John ? You will be happy to learn that I just updated the spkg and that it should be compatible with both both Mac and Linux. Could you give it a try ? :-)
Nathann
comment:49 Changed 8 years ago by
- Keywords Cernay2012 added
- Summary changed from Updated CBC spkg (Cernay 2012) to Updated CBC spkg
Changed 8 years ago by
comment:50 Changed 8 years ago by
- Description modified (diff)
comment:51 Changed 8 years ago by
- Description modified (diff)
(the fix that was contained in note.patch
, a
write_lp
method and some broken doctests...It's moviiiiiiiiiiiing `:-P )
Changed 8 years ago by
comment:52 in reply to: ↑ 48 ; follow-ups: ↓ 53 ↓ 54 Changed 8 years ago by
- Status changed from needs_review to needs_info
Replying to ncohen:
Wouhouuuuuuuuuuuuuu !!!
John ? You will be happy to learn that I just updated the spkg and that it should be compatible with both both Mac and Linux. Could you give it a try ?
:-)
Nathann
I haven't tried Mac yet. On Linux, I'm getting a doctest failure:
sage -t "devel/sage-main/sage/numerical/optimize.py" GLPK Simplex Optimizer, v4.44 6 rows, 3 columns, 8 non-zeros Preprocessing... 2 rows, 2 columns, 4 non-zeros Scaling... A: min|aij| = 2.400e+01 max|aij| = 5.000e+01 ratio = 2.083e+00 GM: min|aij| = 8.128e-01 max|aij| = 1.230e+00 ratio = 1.514e+00 EQ: min|aij| = 6.606e-01 max|aij| = 1.000e+00 ratio = 1.514e+00 Constructing initial basis... Size of triangular part = 2 * 0: obj = -5.100000000e+01 infeas = 0.000e+00 (0) * 1: obj = -5.225000000e+01 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND ********************************************************************** File "/atlas/sage-4.8/devel/sage-main/sage/numerical/optimize.py", line 728: sage: all([ (v in b1 or v in b2 or v in b3) for v in values ]) Expected: True Got: False **********************************************************************
Is that something we need to worry about?
comment:53 in reply to: ↑ 52 Changed 8 years ago by
Is that something we need to worry about?
Well, it is not something that should prevent us from sleeping, but I'd say it comes from the fact that the method returns the LP variables equal to one, and that one of them is equal to 0.9999999 :-)
So we should not worry about that, but definitely fix it.. The weird thing is that I believed I had made the MIP class round the values before returning them ^^;
Nathann
comment:54 in reply to: ↑ 52 ; follow-up: ↓ 55 Changed 8 years ago by
Replying to john_perry:
I haven't tried Mac yet. On Linux, I'm getting a doctest failure:
I don't get the same doctest on Mac.
On Linux, I see what you're talking about. So, is this a bug with the current patch? Is it something I should fix in the Osi patch?
comment:55 in reply to: ↑ 54 ; follow-up: ↓ 56 Changed 8 years ago by
I don't get the same doctest on Mac.
On Linux, I see what you're talking about. So, is this a bug with the current patch? Is it something I should fix in the Osi patch?
Well, I expect that such noise isplatform dependent, and that it is the reason why it has not been patched already. Could you check that it is indeed a rounding problem ? I thought the solver interfaces had all been asked to round the values of integer-type variables, but if it is not the case this should be done for GLPK (trivial stuff).
About whether we should create a new ticket for that, it is as you prefer. We can also put it discretely in this patch as it should not wait for too long before it can be merged :-)
Nathann
comment:56 in reply to: ↑ 55 ; follow-up: ↓ 57 Changed 8 years ago by
Replying to ncohen:
Well, I expect that such noise isplatform dependent...
That wouldn't surprise me. In fact, I am working on a machine that I didn't have the last time I tried this patch on Linux, which is probably the reason it occurred.
Could you check that it is indeed a rounding problem ?
What exactly should I check? I traced through the code, and found that one of the box
es contains the following result:
{0: {0: 1.0, 1: 0.0, 2: 0.0}, 1: {0: 0.0, 1: 0.0, 2: 1.0}, 2: {0: 0.0, 1: 0.0, 2: 1.0}, 3: {0: 0.0, 1: 0.99999999999999989, 2: 0.0}, 4: {0: 1.0, 1: 0.0, 2: 0.0}}
Once I saw the 0.999... I figured you knew what the issue was better than I. :-)
I thought the solver interfaces had all been asked to round the values of integer-type variables, but if it is not the case this should be done for GLPK (trivial stuff).
I was under the impression that Cbc was called as the default solver when it's installed, so wouldn't that be the one to patch? or am I wrong?
comment:57 in reply to: ↑ 56 ; follow-up: ↓ 58 Changed 8 years ago by
I was under the impression that Cbc was called as the default solver when it's installed, so wouldn't that be the one to patch? or am I wrong?
Well, it should, but the code you put in your former message contains a big "GLPK" so I assumed it was the solver that was being used.... So you tell me ^^;
If it comes from CBC (which would mean that I was right when I thought that GLPK rounded its values before returning them), then it should indeed do the same :-)
Nathann
comment:58 in reply to: ↑ 57 Changed 8 years ago by
Replying to ncohen:
I was under the impression that Cbc was called as the default solver when it's installed, so wouldn't that be the one to patch? or am I wrong?
Well, it should, but the code you put in your former message contains a big "GLPK" so I assumed it was the solver that was being used.... So you tell me
^^;
That's quite interesting. Cbc is definitely the default (I just had an error on a program b/c I tried preprocessing
which works only for GLPK) but I'm still getting the GLPK. I don't understand the error.
I'll try to figure out what's going on; it'll take a bit, though, because of the other program...
comment:59 follow-up: ↓ 60 Changed 8 years ago by
Nathann, I asked sage to put print Coin
or GLPK
, depending on which was initialized, and the the output is Coin
. So the coin_backend
is being initialized.
I think the GLPK
output is from a different test in the same file (line 481, for linear_program()
).
So the problem seems to be the Coin patch in this case. I'll look for how to fix it, but if you have suggestions, let me know.
comment:60 in reply to: ↑ 59 Changed 8 years ago by
So the problem seems to be the Coin patch in this case. I'll look for how to fix it, but if you have suggestions, let me know.
Well, I usually fix this twice : by relacing the ==1
in the return value by of the method building the LP by a
>.5
, and by adding a "if the variabe is binary, round it before returning it" in the functon returning the values of variables in the solver backends.
Nathann
comment:61 Changed 8 years ago by
I see that binpacking()
sets the variable to binary, but I don't see any rounding in any of the backends. I do see that in the coin_backend
we have (line 252)
elif vtype == 0: self.si.setColLower(variable, 0) self.si.setInteger(variable) self.si.setColUpper(variable, 1)
which sets the binary variable.
If I infer correctly, it's optimize.py
that should be patched, so that binpacking
checks the rounded result, and not a clear 1
?
comment:62 Changed 8 years ago by
Helloooooooo !!
Well, actually I only did it for Gurobi and CPLEX :-)
It looks like it should also be done for GLPK (which until now seemed to round it by itself, as no doctest broke), and most probably for Coin ^^;
Nathann
comment:63 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
I'm attaching a slightly different approach. I see what you did in CPLEX, but I think a more efficient approach is for the client should do the rounding if it wants that. This avoids the function call to the backend to determine whether the variable is continuous. After all, the client already knows that.
Changed 8 years ago by
comment:64 Changed 8 years ago by
- Description modified (diff)
But, if you prefer, I've also attached a patch that rounds within coin itself. That's the ...coin_rounding.patch
.
I tested GLPK by explicitly setting the solver in binpacking
, and had no trouble. So it doesn't seem to need modification (though I can add that, too, if you like).
comment:65 Changed 8 years ago by
- Description modified (diff)
Changed 8 years ago by
comment:66 Changed 8 years ago by
I have no idea why the earlier version of the binpacking_rounding
patch was empty. Try it now.
comment:67 Changed 8 years ago by
Well, both are good answers `:-)
Nathann
comment:68 follow-up: ↓ 69 Changed 8 years ago by
Helloooooooooo John ! :-)
When I try these patches and the new spkg 2 errors remain in coin_backend.pyx. The first one is not important (a variable n that represents a string has been declared as a C integer, it is fixed in a split second), and the other is in the copy() function. It looks like the "copied" object is empty (zero constraints, and p.solve() returns 0, ...). Do you know where this could come from ? O_o
Oh, and also : why do you want to cache all the values of the variables in a dictionnary attached to the CoinBackend? object ? To me it is doing too much work, as the user does not always want to read ALL the variables (some are just there to define constraints) and sometimes none at all (just interested in the optimal value of the LP, or in its feasibility). The other point is that storing values in Python lists is *MUCH* more expensive than storing them in C arrays. Because a dictionnary is expensive, and because it does not store C floats but pointers to Object representings floats.... :-P
It would be nice to see this patch merged in Sage 5.0. Anyway thanks for all the work you did on this ticket :-)
Nathann
comment:69 in reply to: ↑ 68 ; follow-up: ↓ 70 Changed 8 years ago by
Replying to ncohen:
When I try these patches and the new spkg 2 errors remain in coin_backend.pyx. The first one is not important (a variable n that represents a string has been declared as a C integer, it is fixed in a split second)...
Can you tell me which one?
...and the other is in the copy() function. It looks like the "copied" object is empty (zero constraints, and p.solve() returns 0, ...). Do you know where this could come from ?
O_o
Since Cbc becomes the default solver when you install coin, I recently noticed that after copying and trying to change the objective function, Sage would crash, hard. In fact, I was thinking of that this morning before I came down to the computer.
I am not sure what is going on. I know it used to work some time ago, since as you know I had been very interested in making Cbc work at one point. I'm planning to look at it again, though since GLPK is now working I was busy working on my research instead. Just this week I've arrived at a point on the problem I was studying that I think I can look at this again, so I will try to fix it.
Oh, and also : why do you want to cache all the values of the variables in a dictionnary attached to the CoinBackend? object ?
If I want to add a constraint after solving once, the Cbc model crashes, hard. I don't remember if it crashes when I add to the model, or when I try to solve. The solution I had found, and which worked at one point, was to delete the model, but since OsiClp? stores the solution in the model (no joke) you lose the solutions. My solution was to store the values of the variables; I don't remember how, but a dictionary doesn't sound too wrong...
Do you think I should store them in C floats? Do you have a better suggestion?
It would be nice to see this patch merged in Sage 5.0. Anyway thanks for all the work you did on this ticket
:-)
I know. I'll try to work on it, but I have no guarantees that I'll have a patch soon.
john
comment:70 in reply to: ↑ 69 Changed 8 years ago by
Helloooooo !!!
Can you tell me which one?
Oh sorry, it is in the one-line patch I just attached to this ticket.
Since Cbc becomes the default solver when you install coin, I recently noticed that after copying and trying to change the objective function, Sage would crash, hard. In fact, I was thinking of that this morning before I came down to the computer.
Hmmm... Did you update Sage to some 5.0 beta in between ? Odd thing O_o
I am not sure what is going on. I know it used to work some time ago, since as you know I had been very interested in making Cbc work at one point. I'm planning to look at it again, though since GLPK is now working I was busy working on my research instead.
Well, I'm applying for a permanent position myself and it is taking most of my life ^^;
Just this week I've arrived at a point on the problem I was studying that I think I can look at this again, so I will try to fix it.
Same thing here. I may have one week and perhaps a bit more to do my job *mathematics*. And some time for Sage too :-)
Oh, and also : why do you want to cache all the values of the variables in a dictionnary attached to the CoinBackend? object ?
If I want to add a constraint after solving once, the Cbc model crashes, hard. I don't remember if it crashes when I add to the model, or when I try to solve.
If I remember correctly it is when you try to solve it.
The solution I had found, and which worked at one point, was to delete the model, but since OsiClp? stores the solution in the model (no joke) you lose the solutions.
Yeah I know, that's the reason why you can not add constraint, then solve, then add constraints, then solve again. Because if the first "solve" operation said that some variable had a value of 1.7, this variable has an upper bound and a lower bound of 1.7 after the first call to solve. That's awful.
My solution was to store the values of the variables; I don't remember how, but a dictionary doesn't sound too wrong...
Do you think I should store them in C floats? Do you have a better suggestion?
Well, then that is a problem when the user wants to 1) solve a LP 2) add a constraint 3) read the value given to the variables by the *former* call to solve. Actually I mostly wondered about whether we should cache them ourselves at all. In the user backends (that's not necessarily relevant of course, given Coin's "own constraints") the solutions are just "stored by the LP", as it is done by Coin. As it is more expensive to store them in a dictionary that through Coin's internal storage system, I would rather stand for an exception raised in the situation where the user goes through the 3 steps I listed before. "If Coin has no variable in memory for some reason, raise an exception saying so". And in this situation the user is free to build his own dictionary before adding constraints so as to remember them while adding new constraints.
All in all, if we are decided to cache it a dictionary is probably the best -quick and easy- solution. But this really is not something Sage should do, that's the solver's job...
I know. I'll try to work on it, but I have no guarantees that I'll have a patch soon.
I will be thinking about this patch too, but it really is tricky. I mean..... Considering the solver's behaviour, I have to admit that I hate to have to do dirty work above to patch their mistakes :-/
Nathann
Changed 8 years ago by
comment:71 Changed 8 years ago by
- Status changed from needs_review to needs_work
Well.... If instead of calling self.si.clone() we call self.si.clone(1), the problem is solved. This patches folds the previous ones, and *all tests pass*. I will continue to study the code, though.... :-)
Nathann
Changed 8 years ago by
comment:72 Changed 8 years ago by
- Description modified (diff)
comment:73 follow-up: ↓ 74 Changed 8 years ago by
Ok, there was a stupid error in a doctest of GenericGraph?.maximum_average_degree which was just a bad rounding. With this new patch, there is no problem with the doctests of graph/ either.
Tell me John : instead of copying the whole solution inside of the Python structure, what would you think of just storing the "model" object ? As you do, it could be automatically destroyed when the LP is changed, actually all that you do with .solutions could be done with .model, and then we would not have to copy solutions over and over ? What do you think ? :-)
I am glad that this updated spkg at least passes all tests..... :-)
Nathann
comment:74 in reply to: ↑ 73 ; follow-up: ↓ 76 Changed 8 years ago by
Replying to ncohen:
Well.... If instead of calling self.si.clone() we call self.si.clone(1), the problem is solved.
Oh, wow. Seriously: wow. I thought that took care of itself; after all, the C++ signature is
virtual OsiSolverInterface * clone(bool copyData = true) const = 0;
so shouldn't copyData
be initialized to true
if it isn't? or could it be Cython that's sending a default value of 0? (maybe the new version? the new Cython has several regressions from my point of view, though the developers call them bug fixes. ;-)
) Seriously, this worked for me once. I wonder if it worked when I put in 1
& then thought it was something else...
Replying to ncohen:
Tell me John : instead of copying the whole solution inside of the Python structure, what would you think of just storing the "model" object ? As you do, it could be automatically destroyed when the LP is changed, actually all that you do with .solutions could be done with .model, and then we would not have to copy solutions over and over ? What do you think ?
:-)
Are you sure the model is automatically deleted? Currently, our code deletes it (new line 692). I wouldn't want to introduce a new memory leak. Otherwise, I don't object at all.
I am glad that this updated spkg at least passes all tests.....
:-)
Yeah, thanks for that. I seriously hadn't been able to get to that; I had hoped to take care of it yesterday myself, but I got so bogged down in trying to find a simple example of cycling in simplex that I never had the chance.
Meanwhile, I've discovered a new GLPK bug; I'll tell you about it in email, though.
Hey, I just noticed the new trac puts a preview of the message beneath the text box. Awesome.
On the other hand, Firefox just crashed, too. Argh...
Changed 8 years ago by
comment:75 Changed 8 years ago by
- Description modified (diff)
comment:76 in reply to: ↑ 74 ; follow-up: ↓ 77 Changed 8 years ago by
so shouldn't
copyData
be initialized totrue
if it isn't? or could it be Cython that's sending a default value of 0?
Yep, looks like that was the problem. Hopefully I did not know (or either forgot) that the default value was specified there or I would not have thought of changing it ! :-p
Are you sure the model is automatically deleted? Currently, our code deletes it (new line 692). I wouldn't want to introduce a new memory leak. Otherwise, I don't object at all.
Well, when you add a constraint to the LP you call sage_free(self.solutions), so what about replacing that by del self.model ? If there is no way to do that without introducing a memory leak, we will just refrain from doing it :-D
Yeah, thanks for that. I seriously hadn't been able to get to that; I had hoped to take care of it yesterday myself, but I got so bogged down in trying to find a simple example of cycling in simplex that I never had the chance.
Ahah. Well, today is a *good* day. With my interview behind me, I just have useful work to do, and it feels great ! Of course I also spent some time tracking nasty bugs :-p
Nathann
comment:77 in reply to: ↑ 76 Changed 8 years ago by
Replying to ncohen:
Yep, looks like that was the problem. Hopefully I did not know (or either forgot) that the default value was specified there or I would not have thought of changing it !
:-p
I wouldn't have thought of it. I'm quite certain that worked once.
Are you sure the model is automatically deleted? Currently, our code deletes it (new line 692). I wouldn't want to introduce a new memory leak. Otherwise, I don't object at all.
Well, when you add a constraint to the LP you call sage_free(self.solutions), so what about replacing that by del self.model ? If there is no way to do that without introducing a memory leak, we will just refrain from doing it
:-D
I'm okay with del self.model
, as long as it's in there. :-)
Ahah. Well, today is a *good* day. With my interview behind me, I just have useful work to do, and it feels great ! Of course I also spent some time tracking nasty bugs
:-p
I hope the interview has a good result! and now I'd better get to writing that email...
comment:78 follow-up: ↓ 80 Changed 8 years ago by
Hellooooooo John !!
Here is a new patch without cached "solution" parameters... But there is one thing I do not understand : with or without this patch constraint generation does not work with Cbc, so what was the point of caching these informations in the first place ? It is still useless to try to solve a LP, then change some parameters, then solve it again ! So why ? O_o;
Nathann
comment:79 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:80 in reply to: ↑ 78 ; follow-up: ↓ 81 Changed 8 years ago by
Replying to ncohen:
with or without this patch constraint generation does not work with Cbc, so what was the point of caching these informations in the first place ?
The OsiClpInterface
doesn't store solutions generated by the model, so if the solutions aren't cached, they're lost as soon as model
is deleted.
john
comment:81 in reply to: ↑ 80 ; follow-up: ↓ 82 Changed 8 years ago by
The
OsiClpInterface
doesn't store solutions generated by the model, so if the solutions aren't cached, they're lost as soon asmodel
is deleted.
But why didn't you want to keep only one self.model object from the beginning then ? O_o;
Nathann
comment:82 in reply to: ↑ 81 Changed 8 years ago by
Replying to ncohen:
The
OsiClpInterface
doesn't store solutions generated by the model, so if the solutions aren't cached, they're lost as soon asmodel
is deleted.But why didn't you want to keep only one self.model object from the beginning then ?
O_o;
I believe it crashes when you try adding constraints & solving the model w/new constraints.
comment:83 Changed 8 years ago by
Ahaah ! Looks like you are right... Well, then I guess this patch finally passes all tests, and so is ready for review ! I updated the last one, and removed some old comments :-)
Nathann
comment:84 follow-up: ↓ 85 Changed 8 years ago by
Before I review this: I see that I have several different patches applied. If I understand correctly, the patches you have just uploaded take care of all those, plus the fixes you mention today?
comment:85 in reply to: ↑ 84 Changed 8 years ago by
Before I review this: I see that I have several different patches applied. If I understand correctly, the patches you have just uploaded take care of all those, plus the fixes you mention today?
Yep ! All Jeroen will have to merge to Sage from this ticket is the set of three patches listed after "APPLY" in the ticket's section. The first of those is a folding of the different patches we wrote while working on this ticket.
Nathann
comment:86 follow-up: ↓ 87 Changed 8 years ago by
- Status changed from needs_review to needs_work
I know this is a minor thing, but would you mind changing
range(number)
toxrange(number)
incoin_backend.pyx
?- adding me as an author? I forgot to do that in the patches I originally submitted (& some work is mine)
Otherwise, this is okay, & I would give it a positive review if I could. Though I still want to test it on a Mac when I get a chance, since things sometimes act funny there.
comment:87 in reply to: ↑ 86 ; follow-up: ↓ 88 Changed 8 years ago by
- Reviewers set to John Perry, Nathann Cohen
- Status changed from needs_work to needs_review
Hellooooooo !!!
range(number)
toxrange(number)
incoin_backend.pyx
?
Hmmmm... You think it is faster ? I thought that the "for i in range(n)" were directly translated to C loops when used in a Python file.
Actually, you can do "sage -cython -a file.pyx" to see that. It creates a html file from the pyx file, and you can see by double-clicking on a line how it is translated in C :-)
- adding me as an author? I forgot to do that in the patches I originally submitted (& some work is mine)
Oh sorry ! You mean in the HG patches ? Actually the "all tests pass" contains only your name as the author (I folded many patches and the first one was probably yours) :-)
Otherwise, this is okay, & I would give it a positive review if I could. Though I still want to test it on a Mac when I get a chance, since things sometimes act funny there.
No problem ! I am glad to this this nightmarish ticket (almost) settled :-)
Nathann
comment:88 in reply to: ↑ 87 ; follow-up: ↓ 89 Changed 8 years ago by
- Status changed from needs_review to positive_review
Replying to ncohen:
range(number)
toxrange(number)
incoin_backend.pyx
?Hmmmm... You think it is faster ? I thought that the "for i in range(n)" were directly translated to C loops when used in a Python file.
In Python, range(number)
creates a list of numbers from 0 to n-1
, while xrange(number)
is supposed to be more efficient if you don't need the list.
But, you're right about Cython. I looked at the annotated html, and Cython is smart enough not to build the list. So it isn't a problem after all. I had just never checked that before, and assumed that Cython built the list just as Python did.
- adding me as an author? I forgot to do that in the patches I originally submitted (& some work is mine)
Oh sorry ! You mean in the HG patches ? Actually the "all tests pass" contains only your name as the author (I folded many patches and the first one was probably yours)
:-)
Not my name in the patch, but my name in the source code. The source code for coin_backend.pyx
doesn't list me as an author. It's only:
""" COIN Backend AUTHORS: - Nathann Cohen (2010-10): initial implementation """
I'm giving it a positive review anyway (it passes the doctests, even on a mac), but please consider it.
john
Changed 8 years ago by
comment:89 in reply to: ↑ 88 Changed 8 years ago by
Not my name in the patch, but my name in the source code. The source code for
coin_backend.pyx
doesn't list me as an author.
Oops sorryyyyyyyyyyyy !! I just uploaded a patch that adds your name at the top of the file, and if you do not like what I wrote there please change it whenever you want, in this ticket or later on :-)
And thank you very much for your work on this ticket !!! I would have lost hope ten times if I had had to do it alone :-D
Nathann
comment:90 Changed 8 years ago by
- Component changed from linear programming to optional packages
comment:91 follow-up: ↓ 92 Changed 8 years ago by
LOL, you didn't have to say major modifications...
comment:92 in reply to: ↑ 91 Changed 8 years ago by
LOL, you didn't have to say major modifications...
Well, it has all the characteristics of a "major" modifications
1) I gave up ten times since the ticket was opened 2) I have no idea what the code looked like before 3) I am happy that it is now behind us and I never want to touch this file again
:-D
Nathann
comment:93 Changed 8 years ago by
- Merged in set to sage-5.0.beta13
- Resolution set to fixed
- Status changed from positive_review to closed
I sent a message to Harald Schilly to put this on the mirrors, so it should be there soon.
comment:94 follow-up: ↓ 95 Changed 8 years ago by
mirror magic just happened and congrats to this impressive ticket!
comment:95 in reply to: ↑ 94 Changed 8 years ago by
mirror magic just happened and congrats to this impressive ticket!
... And all Hail to Harald's magic ! :-D
Nathann
What needs work? (I haven't look at it yet, sorry if it's obvious.)
Also, are we going to change in this ticket from OsiCbc? to plain Cbc?