[gecode-users] (no subject)

[Mikael Zayenz Lagerkvist]

On Feb 10, 2008 9:48 AM, Malcolm Ryan <malcolmr at cse.unsw.edu.au> wrote:
> Suppose I have variables X1 ... Xn and Y1 ... Yn, with the constraints
>
> distinct(X1, ..., Xn)
> distinct(Y1, ..., Yn)
>
> I now want to add the constraint:
>
> Yi notin {Xj | j != i}, for i = 1 ... n
>
> What would be the most efficient way to do this?
>
> I could, of course, express it as:
>
> Yi != X0
> Yi != X1
> ...
> Yi != Xi-1
> Yi != Xi+ 1
> ...
> Yi != Xn
>
> The downside of this is that it would introduce a bunch of boolean
> variables to keep track of.

Why would this add any extra Boolean variables? As far as I can see,
it is just a bunch of very simple propagators (the decomposition of
the constraint distinct(X1, .., Xi-1, Yi, Xi+1, ... Xn)).


> Alternatively. I could say:
>
> distinct(X1, .., Xi-1, Yi, Xi+1, ... Xn)
>
> which is overkill, but doesn't add any extra constraints that are not
> already covered by the original distinct(X1, ..., Xn) constraint.

With domain consistency, this model would do more pruning than the
above decomposition. Consider variables x1,x2,x3 and y1,y2,y3 with
domains
    x1,y2 in {1,2}
    x2,x3,y1,y3 in {1,2,3}
then the constraint
    distinct(x1,y2,x3)
would assign x3 the value 3, even though none of the variables is
assigned and neither distinct(x1,x2,x3) nor distinct(y1,y2,y3) would
prune anything.

On the other hand, there is a large number of such constraints, and
the overhead might not be worth the potential extra pruning.


> Any suggestions as to which is likely to be better? Or is there
> another way?

I think you just have to test how the different models work in you
specific case. I would suggest that you distinct with all the
different levels of pruning, as well as the decomposition.


Hope this helps,
Mikael

-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/