Updated CBC spkg

[ncohen]

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:

• trac_12220-all_tests_pass.patch​
• trac_12220-mad+doc.patch​
• trac_12220-nocache.patch​

[john_perry]

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?

[ncohen]

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

[john_perry]

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.

[john_perry]

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?

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

[john_perry]

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 ctypedefs supposed to go in a certain order? Cython documentation doesn't seem clear on this.

[john_perry]

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

[ncohen]

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

[john_perry]

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

[john_perry]

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

[ncohen]

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

[john_perry]

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.

[john_perry]

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.

[ncohen]

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

[john_perry]

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

[john_perry]

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

[john_perry]

BTW, it looks (from example driver3.cpp) that I won't have to complete rewrite the whole thing.

[john_perry]

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

[john_perry]

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.

[john_perry]

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.

[john_perry]

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.

[john_perry]

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.

[john_perry]

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?

[ncohen]

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

[john_perry]

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.

1. let si = new OsiClpSolverInterface?()
2. while not done:
   1. add constraints, variables, whatnot to si
   2. let model = new CbcModel?(si)
   3. model.branchAndCut()
   4. 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.

[ncohen]

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

[ncohen]

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

[john_perry]

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

[ncohen]

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

[john_perry]

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.

[john_perry]

Good news and bad news.

1. setModelOwnsSolver() allows me to retain the solver interface after CbcModel finishes with it. I can get solutions, even add new constraints.
2. 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!'

3. There are no examples of using either setModelOwnsSolver() or assignSolver().

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.

[john_perry]

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?

[john_perry]

uses CbcModel? along with OsiClpSolverInterface?

[john_perry]

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.

[john_perry]

Whoops -- forgot to change the instructions!

[john_perry]

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

[john_perry]

(I wish there were a way to delete attachments!)

[ncohen]

(let's not forget that)

Nathann

[john_perry]

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?

[ncohen]

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

[john_perry]

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

[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 ?

Nathann

[john_perry]

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

[ncohen]

(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

[john_perry]

Replying to ncohen:

Then we build the coin_backend.pyx file in Sage...

Okay, duh, that's the part I overlooked. :-D

[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

[ncohen]

(the fix that was contained in note.patch, a write_lp method and some broken doctests...It's moviiiiiiiiiiiing `:-P )

[john_perry]

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?

[ncohen]

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

[john_perry]

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?

[ncohen]

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

[john_perry]

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 boxes 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?

[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 ^^;

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

[john_perry]

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

[john_perry]

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.

[ncohen]

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

[john_perry]

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?

[ncohen]

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

[john_perry]

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.

[john_perry]

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

[john_perry]

I have no idea why the earlier version of the binpacking_rounding patch was empty. Try it now.

[ncohen]

Well, both are good answers `:-)

Nathann

[ncohen]

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

[john_perry]

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

[ncohen]

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

[ncohen]

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

[ncohen]

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

[john_perry]

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

[ncohen]

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?

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

[john_perry]

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

[ncohen]

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

[john_perry]

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

[ncohen]

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.

But why didn't you want to keep only one self.model object from the beginning then ? O_o;

Nathann

[john_perry]

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 as model 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.

[ncohen]

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

[john_perry]

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?

[ncohen]

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

[john_perry]

I know this is a minor thing, but would you mind changing

• range(number) to xrange(number) in coin_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.

[ncohen]

Hellooooooo !!!

• range(number) to xrange(number) in coin_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

[john_perry]

Replying to ncohen:

• range(number) to xrange(number) in coin_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

[ncohen]

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

[john_perry]

LOL, you didn't have to say major modifications...

[ncohen]

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

[jdemeyer]

I sent a message to Harald Schilly to put this on the mirrors, so it should be there soon.

[schilly]

mirror magic just happened and congrats to this impressive ticket!

[ncohen]

mirror magic just happened and congrats to this impressive ticket!

... And all Hail to Harald's magic ! :-D

Nathann