[Gecode] Equality, variable aliasing and AllDistinct

[Christian Schulte]

Good point, I was refering to integer problems. Actullay, doing it is not
difficult... But there are more intersting things to do than that.

Combinators is one. However, we will only start after the first milestone,
where we are sure that the kernel and the libraries have the right structure
without combinators. I think we are there right now and the next thing is
writing papers and documentation. Actually, the first paper using and
mentioning Gecode will be accepted for toplas anytime soon...

Christian

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

-----Original Message-----
From: duchier at ps.uni-sb.de [mailto:duchier at ps.uni-sb.de] 
Sent: Thursday, May 27, 2004 11:12 AM
To: schulte at imit.kth.se
Cc: Technical discussions about Gecode
Subject: Re: [Gecode] Equality, variable aliasing and AllDistinct


"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