[Gecode] Equality, variable aliasing and AllDistinct

[Christian Schulte]

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).

The other aspect is how to implement variable variable equality. There the
solution which is good for data structures (realising it in the store) is
required for entailment. With propagation only it does not make sense: a
propagator has to always rediscover from the store which aliasing happened. 

A solution which we might want to explore in the future is a substitution
based approach: aliasing two variables will eliminate one and will replace
in all occurrence (read propagators) one by the other. Here the information
for which propagators substitution has to be performed is directly
available. Another aspect is factorization: with substitution, aliasing
becomes a completely orthogonal aspect to both propagation and how variables
are implemented! Data structures such as variable arrays storing solutions
then have to be equipped with a propagator maintaining aliased variables.

This is quite interesting and a new idea, however the benefits might be not
that large.

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: gecode-bounces at ps.uni-sb.de [mailto:gecode-bounces at ps.uni-sb.de] On
Behalf Of Guido Tack
Sent: Thursday, May 27, 2004 10:31 AM
To: Technical Discussions about Gecode
Subject: [Gecode] Equality, variable aliasing and AllDistinct


Hi!

In a discussion with Thorsten and Didier, a technical question came up:

In Mozart, {FD.distinct [A B C]} will immediately detect failure if A=B.
This 
is not the case for Gecode, where A=B just posts a propagator instead of 
identifying the two variables. I know from a discussion with Christian that 
he thinks that identifying variables in the store is a bad thing because it 
makes the system much more complicated. So the question was whether there is

either a simple solution that enables distinct to test for aliasing, or 
whether this is a border case that is not interesting in practical 
applications.

	Guido

-- 
Guido Tack
Programming Systems Lab
http://www.ps.uni-sb.de/~tack
_______________________________________________
Gecode mailing list
Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode