[Gecode] Re: Nary partition etc.

[duchier at ps.uni-sb.de]

[I am forwarding to the gecode list - keep ALL gecode related
 discussions on that list - come on - how many times does this need to
 be said?]

Guido Tack <tack at ps.uni-sb.de> writes:

> Do you know of some formal write-up of the propagation rules for an n-ary 
> partition (union, intersection etc.) propagator? If not, do you think we 
> should look at the Mozart source code or rather synthesize the rules 
> ourselves?

I don't personally know of any write-up, but the obvious formalization
goes as usual, i.e. by formulating expressions that bound each
variable:

S = U+(S1,S2,...,Sn)

glb(S)\U{lub(Sk)|k!+i} <= Si <= lub(S)\U{glb(Sk)|k!=i}
U{glb(Sk)|1=<k=<n} <= S <= U{lub(Sk)|1=<k=<n}

and similarly for cardinality bounds.  Perhaps there are stronger
inferences to be made, but I would have to think about it.

The fundamental implementation issue for the above is to avoid the
quadratic complexity of the naive implementation - use the same trick
family as for n-ary fd constraints.

Cheers,

-- 
Denys Duchier - Équipe Calligramme - LORIA, Nancy, France