|
Hi Guido,
Thanks for looking into this. I think I will leave the ::domain
annotations on alldiff and global_cardinality, until your change
makes it into a release.
Cheers,
Pete
On 28/05/15 10:20, Guido Tack wrote:
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
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
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
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
|
