<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Mar 13, 2014 at 10:53 AM, John Forrest <span dir="ltr"><<a href="mailto:john.forrest@fastercoin.com" target="_blank">john.forrest@fastercoin.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div text="#000000" bgcolor="#FFFFFF">
<div>David,<div class=""><br>
<br>
On 13/03/14 03:59, David Einstein wrote:<br>
</div></div><div class="">
<blockquote type="cite">
<div dir="ltr">Thanks. I was doing the moral equivalent of button
mashing, having only the faintest memory of how Dantzig-Wolfe
worked, and no idea of its applicability. (also apologies for
posting this to Cbc instead of Clp)
<div>
<br>
</div>
<div>Running</div>
<div><br>
</div>
<div><span>clp KCMO.mps.bz2 -idiot 500 -primals</span><br>
</div>
<div><span><br>
</span></div>
<div><span>takes 44 minutes on my machine, about three times as
fast as the default (dual) computation.</span></div>
<div><span><br>
</span></div>
<div><span>If I want to do this with an instance of ClpSimplex,
the cpp dump says</span></div>
<div><span><br>
</span></div>
<div>
<p> clpModel->setPerturbation(50);</p>
</div>
</div>
</blockquote></div>
You may need to set perturbation on <br><div class="">
<blockquote type="cite">
<div dir="ltr"><br>
<div>The options and extra info are mysterious.</div>
</div>
</blockquote></div>
ClpSolve.hpp gives hints - so setting options[1] says use idiot
with the associated extraInfo of 500<div class=""><br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>Would the following accomplish about the same thing?</div>
<div><br>
</div>
<div> ClpSolve clpSolve;</div>
<div> clpSolve.setPresolveType(ClpSolve::presolveOn, 5);</div>
<div> clpSolve.setSolveType(ClpSolve::usePrimalorSprint);</div>
<div> clpSolve.setSpecialOption(1,2,500);</div>
<div> clpModel->initialSolve(clpSolve);</div>
<div><br>
</div>
</div>
</blockquote></div>
Should be OK<div class=""><br>
<blockquote type="cite">
<div dir="ltr">
<div>That I can almost understand. I think.</div>
<div><br>
</div>
<div>Why is starting out with the barrier method entitled
'idiot'? I assume that 'idiot 500' does 500 interior point
steps before passing to the primal simplex.</div>
<div><br>
</div>
<div>Thank you again.</div>
</div>
<div class="gmail_extra"><br>
<br>
</div>
</blockquote></div>
"idiot" is not the barrier method but a cheap imitation - so bad
that I called it the Idiot algorithm and gave a bad talk on it years
ago - any bad heuristic followed by an algorithm is an algorithm.
The simplified basic idea is that you minimize mu*objective + sum of
squared primal infeasibilities. This is done on a very local basis
i.e. column by column where you just solve a quadratic to get new
value. Periodically you reduce mu. For many problems you finish
with a small sum of infeasibilities and an objective a bit higher
than the optimal one. You then finish with primal.</div></blockquote><div><br></div><div>Just a comment. Years ago I tried to reimplement similar ideas as the idiot algorithm, since I observed Clp did very well on problems like quadratic assignment relax. I am sure John has some tricks to make it work, but my experience was it was too unpredictable. For models were it worked very well, you only needed tiny tiny changes in problem structure to make it not work at all. For instance running presolve, which might remove a few linear dependent rows and boom then it didn't work at all. Hence though it worked well in some case, I was unable to find settings which made it usable as to be activated automatically in certain "good" cases. Creating *advanced* starting basis for the simplex algorithm is highly structure dependent and tricky, I don't think anyone has come up with the right idea yet.</div>
<div> </div><div>Anyway just my 2C.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div text="#000000" bgcolor="#FFFFFF"><span class="HOEnZb"><font color="#888888"><br>
<br>
John<br>
<br>
</font></span></div>
<br>_______________________________________________<br>
Cbc mailing list<br>
<a href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a><br>
<a href="http://list.coin-or.org/mailman/listinfo/cbc" target="_blank">http://list.coin-or.org/mailman/listinfo/cbc</a><br>
<br></blockquote></div><br></div></div>