[Cbc] Improving performance for binary model

[Rui Patrocínio]

Hi again,

  After compiling Cbc with Nauty, I got a solution of 298244 in 3 
minutes, which is very nice. This only happens with some additional cuts 
and Vnd heuristic:

-RINS on -Vnd on -probing on -two on -residual on -reduce on -constraint 
on -orbit on

I tried other combinations of parameters and this was the best result by 
far, so I'm not very positive about this. I've to try with other 
instances of the same problem to see if it was just a fluke.

  Anyway, I don't think I'm getting the optimum solution (two hours 
running and no new solutions so far) with this approach.

  I'll try the preprocessing 'trick' next to see if there are some 
improvements.

Best,

Rui Patrocínio


On 11/23/2019 11:15 AM, Rui Patrocínio wrote:
>
> John,
>
>  I also got that solution after two hours while activating some of the 
> cuts and heuristics that are off by default. Can you tell me what you 
> tried related with symmetry? Apparently you got the same solution must 
> faster. After getting that solution, I left it to run for a day and it 
> didn't got any better (not closing the gap). The best solution is a 
> little above 284000 if I remember correctly, so we are not that far 
> away from the optimum.
>
>  Regarding the presolver, I may be able to integrate that "process" 
> (presolving, exporting and presolving again) calling CBC several times 
> while solving our problem, if that helps. I'll make some tests.
>
> Haroldo,
>
>  I could get a valid solution after some minutes, even with the 
> default parameters and activating some of the heuristics and 
> additional cuts helped getting better solutions faster. The manual you 
> linked is useful, obrigado.
>
>  Best regards,
>
> Rui Patrocínio
>
> A 2019-11-23 10:00, John Forrest escreveu:
>
>> My guess is that Cbc is very bad at handling symmetry.  There is a 
>> lot of symmetry and trying some of the ways that Cbc can deal with 
>> symmetry I can get a solution of 296773 fairly quickly, but after an 
>> hour it does not seem to be closing the gap.  The other area where 
>> Cbc is failing somewhat is preprocessing - if I export the model 
>> several times (each time doing presolve) then I can make it smaller - 
>> this obviously wrong.
>>
>> John Forrest
>>
>> On 22/11/2019 15:44, Rui Patrocínio wrote:
>>> Hi,
>>>
>>>   I'm trying to solve one instance of a problem that is taking a 
>>> long time to obtain a good solution. Since all variables are binary, 
>>> probing and implication cuts are doing some work and RINS and Vnd 
>>> are apparently also improving solutions. For other instances of the 
>>> problem we are solving, CBC has an acceptable performance but for 
>>> this instance apparently there's something going wrong (~20 seconds 
>>> to get the optimum solution with a commercial solver versus never 
>>> getting the optimum solution with CBC).
>>>
>>>   If someone can take a look at the model and give me a hint of what 
>>> is going on, I would appreciate it.
>>>
>>>   The model is at 
>>> https://drive.google.com/open?id=1bd4jWONmoyAKIi0oLa-AU-ZTu7_8qhb6
>>>
>>> -- SISCOG - Sistemas Cognitivos, SA
>>>
>>> *Rui Patrocínio*
>>>
>>> _______________________________________________
>>> Cbc mailing list
>>> Cbc at list.coin-or.org <mailto:Cbc at list.coin-or.org>
>>> https://list.coin-or.org/mailman/listinfo/cbc
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org <mailto:Cbc at list.coin-or.org>
>> https://list.coin-or.org/mailman/listinfo/cbc


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20191126/8fcff8fb/attachment.html>