# Re: Alldifferent filtering

From: Joachim Schimpf <j.schimpf_at_icparc.ic.ac.uk>
Date: Wed 16 May 2001 10:50:18 AM GMT
Message-ID: <3B025B6A.CBD6AE59@icparc.ic.ac.uk>
```"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
```
Received on Wed May 16 11:50:40 2001

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:09 PM GMT GMT