[gecode-users] Global cardinality slow

[Guido Tack]

Hi Pete,

actually we’re running over 200 propagators in this case, because the domain consistent gcc with occurrence variables requires no variables being shared, and the sharing in magic sequence is removed by introducing auxiliary variables and posting equality propagators between them… So magic sequence is really the worst case :-(   But at least it explain the millions of propagations.

The better solution is actually to use the bounds consistent propagator, which should be the default for gcc in FlatZinc (and I’ve committed a change to the svn to make it the default).  That one easily solves the problem in under 10 seconds, even on my laptop.

I’ll really have to look into the domain consistent propagator at some point, it seems to have a few serious issues.

Cheers,
Guido

-- 
Guido Tack
http://www.csse.monash.edu/~guidot/



> On 27 May 2015, at 11:24 pm, Peter Nightingale <pwn1 at st-andrews.ac.uk> wrote:
> 
> Hi Guido,
> 
> 1.5 million propagations to reach a fixpoint is a bit odd,  there are only 40 000 domain values and two constraints so I would have guessedthat more than 80000 propagations would be impossible
> 
> By the way I have changed Savile Row to produce ::domain annotations for alldiff and gcc by default. At least then Gecode and Minion will be doing roughly the same thing -- even if it's not a very smart thing. 
> 
> Thanks
> Peter
> 
> On 27/05/15 12:26, Guido Tack wrote:
>> Hi,
>> 
>> thanks for the report, I’ve had a quick look and there seem to be some problems in the algorithm, the 10th fixpoint alone does 1.5 million propagations (so it looks like severely slow convergence), and then later every 6th fixpoint is really slow.  I’ll have to look into this some more but it does look like a bug.
>> 
>> Cheers,
>> Guido
>> 
>> -- 
>> Guido Tack
>> http://www.csse.monash.edu/~guidot/ <http://www.csse.monash.edu/%7Eguidot/>
>> 
>> 
>> 
>>> On 26 May 2015, at 7:39 am, Peter Nightingale <pwn1 at st-andrews.ac.uk <mailto:pwn1 at st-andrews.ac.uk>> wrote:
>>> 
>>> Hi,
>>> 
>>> I'll point this out, it's not really a bug but it's something you might want to look at. The attached flatzinc solves very slowly.
>>> 
>>> At first I had no annotation on the global_cardinality constraint and Gecode took a very long time -- I did not run to completion. I added ::domain to that constraint and it solves in 109 seconds, 981 nodes -- so the time to reach a fixed point at each node is about 1/10th second. Minion solves the equivalent model in 492 left (assignment) branches (I guess the same node count as gecode) and just over 10 seconds -- so I  guess reaching a fixed point in 1/100 s.
>>> 
>>> Does gecode partition the gcc constraint or just remove assigned variables? That might explain the difference with domain consistency
>>> 
>>> Also, did the default propagation level change on gcc? I don't remember this test causing a problem previously.
>>> 
>>> Before you tell me -- I know magic sequence is a stupid benchmark!
>>> 
>>> Cheers,
>>> Pete
>>> <magicSequence.eprime.param.fzn.test0>_______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org <mailto:users at gecode.org>
>>> https://www.gecode.org/mailman/listinfo/gecode-users <https://www.gecode.org/mailman/listinfo/gecode-users>
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20150528/3d1c3a05/attachment.html>