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