Re: Alldifferent filtering

"W.J. van Hoeve" wrote:
> 
> Can you please tell me what kind of filtering Eclipse applies to the
> 'alldifferent' constraint? The documentation states that there are two
> kinds of filtering, AC on the binary decomposition and SOME global
> filtering based on 'exhaustion of all sub-ranges of possible values'.
> These last sentence is a bit vague to me.

The current algorithm is essentially the one described in

%	Jean Francois Puget
%	A fast algorithm for the bound consistency of the alldiff constraint
%	in AAAI 1998.


> The program below shows some behaviour that makes me confused about the
> filtering algorithm.

The algorithm looks mainly at the upper and lower bounds
and does not make all inferences that are possible when
you consider all the "holes" in the domains as well.
That's why you get different results in these cases:

[eclipse 4]: A1::[1,3],A2::[1,3],A3::[2,3],
		fd_global:alldifferent([A1,A2,A3]).

A1 = A1{[1, 3]}
A2 = A2{[1, 3]}
A3 = A3{[2, 3]}

Delayed goals:
        alldifferent([A1{[1, 3]}, A2{[1, 3]}, A3{[2, 3]}], 1)
yes.


[eclipse 5]:  A1::[1,2],A2::[1,2],A3::[2,3],
		fd_global:alldifferent([A1,A2,A3]).

A1 = A1{[1, 2]}
A2 = A2{[1, 2]}
A3 = 3

Delayed goals:
        alldifferent([A1{[1, 2]}, A2{[1, 2]}], 1)
yes.



-- 
 Joachim Schimpf              /             phone: +44 20 7594 8187
 IC-Parc, Imperial College   /            mailto:J.Schimpf@ic.ac.uk
 London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse