[Gecode] Equality, variable aliasing and AllDistinct

[duchier at ps.uni-sb.de]

"Christian Schulte" <schulte at imit.kth.se> writes:

> Not interesting in the least (currently). In particular for distinct I do
> not know about a single example.
>
> However, there are two things to be distinguished here: one is whether it
> makes sense to consider equality between variables as a basic constraint as
> well. Here the answer is that it can make sense, but only in rare cases (the
> cases known are actually Boolean variables with Boolean propagators).

There are many applications in linguistics where (1) identification of
variables make sense, (2) distinctness constraints play an important
role.  For example, when modeling trees, you may want to represent the
"parent" of a node.  In a problem instance, you may have a constraint
that require two nodes A and B to have distinct parents.  If you now
"identify" the two nodes A and B (because that is one of the
composition operations available), you'd like (at least) to discover
failure early rather than late.  In such applications, the benefits
can be quite significant.

Cheers,

PS: on the other hand, if I get to vote, I'd rather see support for
"or"-style combinators first :-)

-- 
Denys Duchier - Équipe Calligramme - LORIA, Nancy, France
AIM: duchierdenys