[Cbc] Bigger paradoxical case for extraVariables option

[John Forrest]

Apologies for long post.

When I ran the problem (with 4 threads) I got -

extrav - 7338 seconds and 10711 nodes
no extrav 5875 seconds and 14445 nodes

so the extra work per node meant that extrav lost out.

One big reason is that until a good solution is obtained, a solve can 
take many iterations with the objective increasing to a very large value.

So it is important to get good heuristic solutions at root node.

Now the feasibility pump heuristic can be very powerful and there are 
many obscure options set by some hocus pocus.  There is a parameter 
pumptune whose default value is (obviously)1005043!  The 1 actually does 
setAccumulate(1) in the feasibility pump heuristic.  In general the 
heuristic is designed for 0-1 problems - if only a small percentage of 
integer variables are general, then it will treat them as continuous and 
then try a small branch and bound to try and fix up.  In this case all 
variables are general so it just exits.

If the 1 is changed to a 5 then it always does the feasibility pump and 
plays some tricks.  So I tried adding -pumptune 5005043 -multiple 4, 
which will do feasibility pump and try four different starting 
continuous solutions in parallel.  With this the extrav run gets a 
reasonable root solution and both improve to 6792 seconds and 5311 seconds.

There still is a problem in that the extra variable was added to improve 
branching, and will probably have a detrimental effect on heuristics.  
So in trunk I have modified code in most heuristics to test - 
isHeuristicInteger.  This should make no difference to the no extrav 
version - but trunk is slightly different in other ways - and any change 
makes a difference (see Haroldo's remarks). So extrav changes to 5479 
seconds while the no extrav gets a bit worse to 5877.

I have not committed changes in trunk.  Anyway, I would recommend change 
to parameters.

John Forrest

On 06/06/16 15:28, acw at ascent.com wrote:
> This is a sequel to a problem I posted about back in April.
>
> I have a 3.4 Mb MPS file that has the following behavior:
>
> cbc -import extrav-test.mps -extrav 10 -solve -quit
>
> takes 9723 CPU seconds to solve, while
>
> cbc -import extrav-test.mps -solve -quit
>
> takes 10850 CPU seconds. The difference is only about 10%, but it's in 
> the wrong direction -- that is, the -extraVariables trick makes it 
> solve slower. In April I presented a similar case, but Dr. Forrest 
> pointed out on that occasion that the solver spent most of its time on 
> heuristics, and the problem was in fact solved by heuristic; 
> apparently introducing the extra variables slows down the heuristic 
> phase.
>
> But the new problem spends most of its time branching, and -extrav 
> still slows it down, though not as dramatically as the earlier 
> problem. I can't send the MPS file to the list because it's too big, 
> but I will be happy to share it with anybody who is willing to take a 
> look.
>
>
> _______________________________________________
> 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/20160613/77ed1675/attachment.html>