[Osi] How to speed-up flop-osi-cbc ?
Renato Bruni
bruni at diei.unipg.it
Wed Sep 30 18:36:46 EDT 2009
Thanks for the answers. I try to summarize a little. I believe that each
solver should have "algorithmic" options (regarding 1. presolver, 2.
cuts generation, 3. branching tree exploration) that greatly affect
performance. Moreover, there are compiler options (-O3, -ffast-math,
etc.) that also affect performance.
We are running some tests with problems like that one in the attached file.
There are 200 binary variables and 50 real ones, 175 setcovering constraints
and 30 other linear constraints. We model it with FlopC++ because we need
such flexibility. Our machine is a 16 processors Xeon 64bit with linux red
hat and compiler gcc. We have solution times of 14 sec. for Cbc, 18 sec.
for Glpk and 1 sec for Cplex. All versions are, more or less, the latest
ones. For bigger problems the relations among times are similar.
We would like to understand if we are using the open source solvers at their
best, or if there is something more that we can do to make them be more
comparable to Cplex.
As for the algorithmic options, we used default by now, because we do not
know how to set them. If I understand correctly, Michal says to reach
algorithmic options for Cbc not via FlopC++ or Osi, but directely on Cbc
via a hack to access the Cbcmodel (getModelPtr() or getRealSolverPtr()).
It seems interesting and we would like to try it (but some things are
unclear to us: in which part of our code we have to access that? Why the
second option is 3 times faster than the first one? Should not be the
same?). Anyway, how do we set them for Glpk (or Symphony)?
John also recommends presolver, but how do we turn presolver on?
And what is the default?
Matthew G., on the other hand, says that this seems not clean, and that if
one is using Osi he should use only that, and remain independent from the
solver. This also seems reasonable, but how do we access the algorithmic
options using FlopC++ and Osi? Is there some documentation? Can
anybody send us an example? Would this be slower than Michal way?
Another point is unclear: some answers suggest the point "using Cbc via
OSI is not recommended!". Why? Does it go slower than normal Cbc?
Or, is it impossible to reach some algorithmic option of Cbc and therefore
it cannot be used at its best? Are there known bugs? And what about Glpk?
As for the compiler options, John and Matthew S. suggest some options.
We tried them, both in the compilation of the libraries (Cbc, Clp, Glpk are
libraries for us) and in the compilation of our code. However, they did not
change things that much (less than 2% of the time). The only option making a
difference seems (obviously) to pass form the optimized version (-O3) to the
debug one of Cbc and Clp (about 4 times slower). Is this coherent with your
experience? Is there some other breakthrough flag that was still not
mentioned? Can anybody send us an example makefile?
Since we have a multiprocessor machine, we would like to use it fully.
Cplex seems to supports this. Which is the situation for the open source
solvers? How do we turn this on, in case? We could not find documentation
on this.
Sorry for the long mail, but I just would like to use open source
solvers at their best.
I hope I did not misunderstood some of your words.
Thanks again for your help and best regards,
Renato
----- Original Message -----
From: "Matthew Galati" <Matthew.Galati at sas.com>
To: "Michal Kaut" <mail at michalkaut.net>; <bruni at diei.unipg.it>
Cc: <osi at list.coin-or.org>; <flopcpp at list.coin-or.org>
Sent: Wednesday, September 30, 2009 4:49 PM
Subject: RE: [Osi] How to speed-up flop-osi-cbc ?
Shouldn't all that (see below) be hidden in OsiCbc::solve( )? And use Osi
parameters like for other solvers. What am I missing? Why would a user want
to do all of that to solve an IP, if they are within the Osi framework?
-----Original Message-----
From: osi-bounces at list.coin-or.org [mailto:osi-bounces at list.coin-or.org] On
Behalf Of Michal Kaut
Sent: Wednesday, September 30, 2009 4:09 AM
To: bruni at diei.unipg.it
Cc: osi at list.coin-or.org; flopcpp at list.coin-or.org
Subject: Re: [Osi] How to speed-up flop-osi-cbc ?
As John points out, using OsiCbc is significantly inferior to using
CbcMain* routines, used by the stand-alone Cbc solver. Here is a hack I
am using in my code, including my comments - straight cut&paste from my
code, no guarantee that the comments make sense..
First definition of the used variables:
- 'model' is a FlopC++ MP_model object
- 'pSolver' is a pointer to OsiCbcSolverInterface attached to model
(i.e. model->, casted from OsiSolverInterface to OsiCbcSolverInterface)
I have left all the options I am passing to CbcMain in the code
(including inactive ones), to illustrate how to use it. They work for my
problem, they might be bad for yours. It is important that 'nCbcArgs' is
the number of active arguments.
Any ideas for improving it are welcomed.
---------------------------------------------------------------------
/*
According to the mailing lists, using Cbc via OSI is not recommended!
Instead, one should use the Main0 and Main1 function from CbcSolver.
This should work exactly like the command-line cbc solver.
We can even use the same options as we would do for cbc; the default
setup is then invoked by passing the following:
const char *args[] = {"ProblemName", "-solve", "-quit"};
There are two ways of doing this. The first one is quite simple,
we just call the Main0 and Main1 methods directly on the CbcModel
object of the current OsiCbc solver (accessed as *pSolver->getModelPtr(),
since getModelPtr() returns the pointer and CbcMainX needs the object):
CbcMain0(*pSolver->getModelPtr());
CbcMain1(3, args, *pSolver->getModelPtr());
This works, except that it is more than 3x slower than the next solution.
The alternative is to create a new CbcModel from the current OsiClp
solver, accessed from OsiCbc using getRealSolverPtr().
To copy the solution back to the our OsiCbc solver, we simply fix
all the variables to the obtained solution...
(It is possible to copy the solution without fixing the variables, but
I did not find any way how to update the "best possible" bound - so
the solver would have the correct solution, but a big optimality gap!)
*/
// set the options we know help with this problem
const int nCbcArgs = 13; // number of arguments sent to CbcMain1()
const char *args[nCbcArgs] = {
"SSND_Det", // the name is needed for this to work!
"-heur", "off", // switch off all the heuristics
"-DivingC", "on", // switch on the "Diving Coefficient" heuristic
"-cuts", "off", // switch off all cut generators
"-gomory", "root", // do Gomory cuts in the root node
"-mixed", "on", // do "mixed-integer-rounding cuts" everywhere
//"-log", "2", // logLevel for B&B solver (Cbc) (default = 1)
//"-threads", "2", // number of threads (default = 0)
"-solve", "-quit" // this is obligatory
};
CbcModel model(*(pSolver->getRealSolverPtr()));
CbcMain0(model);
CbcMain1(nCbcArgs, args, model); // this runs the solver
// now fix the variables by changing their bounds
// could use getColSolution() instead of getCbcColLower/Upper
assert (model.getNumCols() == pSolver->getNumCols()
&& "the CbcModel must have the same variables as our solver!");
for (int col = 0; col < model.getNumCols(); col++) {
pSolver->setColBounds(col, model.getCbcColLower()[col],
model.getCbcColUpper()[col]);
}
// in addition, copy the solution basis
// not necessary, but could speed it up (according to Stefan Vigerske)
pSolver->getModelPtr()->setBestSolutionBasis(model.workingBasis());
solve(MINIMIZE); // note that minimize() would call attach again!
---------------------------------------------------------------------
Hope this helps.
As to silencing Cbc, I use
pSolver->getModelPtr()->setLogLevel(0);
again assuming that pSolver is a pointer to OsiCbcSolver interface
Regards,
Michal
John J Forrest wrote:
>
> Renato,
>
> I am not sure what -O2 switches on (or off). If you go into Cbc (or
> other Coin projects) and just do configure and then look at Makefile,
> you will see that they tend to use -O3 and stuff like -ffast-math and
> -fomit-frame-pointer. You may also want to use -march=native. If
> NDEBUG is not defined in your Makefile that would also be a significant
> hit.
>
> I very much dislike OsiCbc but if that is what is being used then you
> may wish to instantiate it with a non-default CbcStrategy object. This
> would allow you to have preprocessing which could help. You can also
> customize that to use more/different cuts and heuristics.
>
> The message level for the OsiCbc object could also be modified before
> handing it to FlopC++.
>
> John Forrest
>
>
>
> *[Osi] How to speed-up flop-osi-cbc ?*
>
>
> *Renato Bruni * to: osi
> 09/29/2009 02:47 PM
>
>
> Sent by: *osi-bounces at list.coin-or.org*
>
>
>
>
>
>
>
> ------------------------------------------------------------------------
>
>
>
> Hello everybody,
>
> we are migrating from Cplex to FlpoC++/Osi/(Cbc or Glpk or Symphony).
> We are currently running some tests, but it seems that we need some advice
> to speed-up the open source solvers.
>
> We are compiling all with gcc with option -O2 (optimization) but it does
> not
> seem much faster than the debug version. Which options would you recommend
> for speed? Also, we tried to disable messages from the solvers with the
> FlopC++ option "silent", but they write the same messages than before.
> Which
> other option we can try? Is there some other speed option (cut
> generation?)
> that maybe is disabled and one should enable? And how? Pointers to some
> documentation are appreciated.
>
> Thanks a lot in advance.
> Best regards,
> Renato Bruni
>
> _______________________________________________
> Osi mailing list
> Osi at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/osi
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Osi mailing list
> Osi at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/osi
_______________________________________________
Osi mailing list
Osi at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/osi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: setcovering.cpp
Type: application/octet-stream
Size: 3411 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/osi/attachments/20091001/6883f3b5/attachment.obj>
More information about the Osi
mailing list