[Cbc] CoinStructuredModel crash

[Bo Jensen]

On Thu, Mar 13, 2014 at 10:53 AM, John Forrest
<john.forrest at fastercoin.com>wrote:

>  David,
>
>
> On 13/03/14 03:59, David Einstein wrote:
>
> 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)
>
>  Running
>
>  clp KCMO.mps.bz2 -idiot 500 -primals
>
>  takes 44 minutes on my machine, about three times as fast as the default
> (dual) computation.
>
>  If I want to do this with an instance of ClpSimplex, the cpp dump says
>
>    clpModel->setPerturbation(50);
>
>      You may need to set perturbation on
>
>
> The options and extra info are mysterious.
>
>     ClpSolve.hpp gives hints - so setting options[1] says use idiot with
> the associated extraInfo of 500
>
>
>  Would the following accomplish about the same thing?
>
>    ClpSolve clpSolve;
>   clpSolve.setPresolveType(ClpSolve::presolveOn, 5);
>   clpSolve.setSolveType(ClpSolve::usePrimalorSprint);
>   clpSolve.setSpecialOption(1,2,500);
>   clpModel->initialSolve(clpSolve);
>
>   Should be OK
>
>  That I can almost understand. I think.
>
>  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.
>
>  Thank you again.
>
>
>  "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.
>

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.

Anyway just my 2C.


>
> John
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20140313/1b1281a8/attachment-0001.html>