[gecode-users] Extra information during propagation

[Christian Schulte]

Hmmm, I would go for more info in the variables. While Gecode's variables
are incredibly slim, a variable always will have a couple of fields (for
Booleans it is for example 5 words, for integers at least 12) that adding
one more field will not hurt much.

I was about to write that advisors will not work but maybe they will: if you
have a UNIFY event and the variable operations emit that event then advisors
should also be executed.

Honestly, what you try to do sounds very scary to me and Gecode has not been
designed with something like that in mind. But: good luck!

Cheers
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Vincent Barichard
Sent: Thursday, January 22, 2009 6:16 PM
To: Christian Schulte; users at gecode.org
Subject: Re: [gecode-users] Extra information during propagation

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



_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users