[Coin-lpsolver] OsiClp/ClpSimplex/clp performance disparity

Tue May 2 10:20:25 EDT 2006

Ojas, Jan-Willem,

When I looked closer it was not quite what I thought.  The difference in 
qap10 was what I thought (and there clp and Clpsimplex were similar).  For 
the others the major difference seems to be because the problems are 
degenerate.  Clp applies a perturbation when it thinks that it is making 
too many zero moves and that is what is happening with the initialSolve 
interface.  However clp executable has initial perturbation switched on 
and looks at the problem and applies a perturbation up front.  This leads 
to a significant reduction in iterations.

Try setting solver.getModelPtr()->setPerturbation(50) (for OsiClp) before 
initial solve.  You may wish to set it back to its original value before 
branch and cut however.

The reason qap10 is faster is because the non Osi interface allows itself 
to use a very dubious crash which works fantastically well on many 
problems.  I am not sure about encouraging people to use it directly from 
Osi land.

If you want to see what a difference some of these things make you can use 
the stand-alone executable to play with.  If you do "clp qap10.mps -idiot 
0 -dualsimplex" you should get slower run.  You will see much bigger 
differences on larger problems e.g. qap15 or nug20.

John Forrest

"Jan-Willem Goossens" <j.goossens at t75.nl> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
05/02/2006 09:23 AM

To
coin-lpsolver at list.coin-or.org
cc

Subject
[Coin-lpsolver] OsiClp/ClpSimplex/clp performance disparity

Hi,

Wouldnt it be a good idea to make the logic of "being clever about
algorithms and initial solutions" identical across
ClpSimplex::initialSolve and OsiClpSolverInterface::initialSolve (possible
even also the clp executable)? Similarly, for ::resolve.

Or is this not possible/desirable?

Regards,

Jan-Willem Goossens

> Ojas,
>
> I will have to run those problems to check but it is probable that the
> clp executable is being clever about algorithms and initial solutions.
> You should be able to get same results with ClpSimplex::initialSolve by
> setting parameters.
>
> Would it be useful if I worked on the interface and documentation for
> part of my DIMACS presentation?
>
> John Forrest
>
>
>
> Ojas Parekh <ojas at mathcs.emory.edu>
> Sent by: coin-lpsolver-bounces at list.coin-or.org
>
> 05/01/2006 10:07 PM
>
> To
> coin-lpsolver at list.coin-or.org
> cc
> Sebastien Siva <ssiva at emory.edu>, Cynthia A Phillips
> <caphill at sandia.gov>
> Subject
> [Coin-lpsolver] OsiClp/ClpSimplex/clp performance disparity
>
>
>
>
>
>
> Hi,
>
>   We've observed appreciable disparities in the performance of
> OsiClpSolverInterface->initialSolve(), ClpSimplex->initialSolve(),
> and the clp executable program.  In particular here are some of our
> observed running times on instances from well-known collections:
>
> collection/file                   clp exec.     ClpSimplex     OsiClp
> -----------------------------     ---------     ----------     ------
> Linderoth-MIP/dano3_4.mps         57.78         151.99         145.44
> Linderoth-MIP/neos-520729.mps      7.70          20.46          20.50
> Linedroth-MIP/qap10.mps            4.00           3.90          51.51
> COIN/Mps/Big/mkc7.mps             21.15         169.08         165.12
>
> All numbers represent seconds on a 2.2Ghz dual core Opteron running a
> SUSE x86_64 Linux distribution using a CVS build of COIN-OR no older
> than a few weeks.  We've also observed comparable ratios on Solaris
> and PPC Mac OS X machines.  We passed no parameters to the clp
> executable other than the file name and used the following code for
> the object oriented interfaces:
>
> ClpSimplex model;
> model.readMps(argv[1]);
> model.initialSolve();
>
> and
>
> OsiClpSolverInterface si;
> si.readMps(argv[1]);
> si.initialSolve();
>
> We have larger instances particular to our application (Sandia Labs'
> PICO combinatorial optimization engine) that have exhibited similar
> behavior: the clp executable performs an order of magnitude better.
> We have tried experimenting with ClpSolve parameters and writing a
> simple heuristic to mimic the clp executable but have been
> unsuccessful in consistently obtaining comparable performance.
> Before proceeding any further I thought it would be a good idea to
> ask the following questions here:
>
> (1) Does the clp executable do any extra preprocessing or
> presolving?  Do you think the gap is explained only by the way in
> which the three interfaces each set their parameters?  If so, which
> parameters are especially critical for the problems above?
>
> (2) I have explored the source code; however, I was wondering if
> there was any documentation that speaks specifically to the
> differences in (in philosophy of) the three interfaces.
>
> (3) PICO currently exclusively relies on the OsiClp interface.  I
> understand that I can use the getModelPtr() method to call
> ClpSimplex's version of initialSolve().  Is there callable access to
> the code that the clp executable uses?
>
> Thanks!
> -Ojas
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
>
>

_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20060502/d6cd66f7/attachment.html>