[gecode-users] Extra information during propagation

[Vincent Barichard]

Hi Christian,

Le mercredi 21 janvier 2009 10:39:22 Christian Schulte, vous avez écrit :
> Hi Vincent,
>
> basically you want to have equivalence (or even equality) reasoning in
> Gecode. Gecode has been explicitly designed to not deal with it. Prior
> systems (logic programming based systems such as SICStus, Eclipse, Mozart,
> ...) do have equality reasoning (but typically with lots of restrictions if
> not bugs). However my own experience has been that it is not useful enough
> (from a general perspective) and the chosen implementation technology
> (maintaining equivalence classes) is totally ill matched to performing
> propagation efficiently.
>

I agree. I don't want to perform a full equality reasoning.

> What would be possible on a general level is to use a substitution based
> approach. We know how to do it but it is a lot of work.
>

That's why I think about a "rewrite" approach where propagators are rewritten 
when they detect that two of their variables are the same.

> Okay that was just the background info and the answer that there is no
> general way and just fixing something in Gecode will not do the trick.
>
> Then what you might want to do is to define a new type of variables
> yourself that just extends Gecode variables by an additional level of
> indirection to do equivalence reasoning.
>

I began something like that. I have a new type of variables and propagators 
over these variables.
When a variable has been found equal to another, I post a "domain equality" 
propagator which ensures that the domains will be always equal. So, normal 
propagators will be  scheduled when domain of one of the two equal variables 
will be updated.

Furthermore, a UNIFY event is emitted. But propagators which are able to deal 
with this event have to know which are the equal variables. How to get this 
piece of information from the propagators?
I think about advisors (with the Delta parameter), but I don't know if it is 
the right choice. I also think about creating an additional field in my new 
variable type, but It will increase the size of the variable (so it will lead 
to increase the cloning time).
I am not sure of how to proceed to get the best efficiency.

> Hope that helps

Yes it helps a lot. Thank you very much.
Vincent