[gecode-users] Extra information during propagation

[Christian Schulte]

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.

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.

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.

Hope that helps
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: Tuesday, January 20, 2009 12:46 PM
To: users at gecode.org
Subject: [gecode-users] Extra information during propagation

Hi,

I try to make a propagator that needs more extra information during 
propagation, but I'm not sure of how to proceed.

For example :

At the begining of the propagation I have a propagator named p2 which
reduces 
domains of a,c,d:

p2(a,c,b)

After some propagation steps, a new propagator is posted (during the 
propagation). This new propagator ensures that: a == b

For my problem, the equality of domains is no sufficient, I really needs to
know 
in the propagation that 'a' is equivalent to 'b'.
Of course p2 is scheduled, but p2 also needs to know that 'a' and 'b' are 
equals to reduce the domain of 'c'. So I want to rewrite p2 by replacing 'a'

with 'b'. It consists in subsuming p2 and posting the new propagator 
p2'(b,c,b) .

I think about two ways of doing this :

First way:
When the propagator 'a == b' is posted (subscribed), it rewrites all the 
propagators which can deal with the equality of two variables 'a' and 'b'.
But 
I needs to know the class of the propagator (only some propagators will be 
able to be rewritten). Is there a way to know (properly) the kind (class) of
a 
propagator? 

Second way:
A new ModEvent will be emitted during propagation when two variables are 
equals. Propagators will deal with this event and will rewrite themselves 
(subsume + post). But during Propagation, extra information is needed (to
know 
with which variable the equality has been found). So I think about advisors 
and read the article "Advisors for Incremental Propagation" but it is said 
that the result of propagation is independent of the state. The problem is 
that if the extra information is not provided, the result of propagation
will 
be different. Indeed, if the propagator doesn't know that 'a == b', it will 
lead to less reducing. Can I still use advisors?

I don't want to make a quick dirty hack (by changing the GeCode code). So
how 
do you proceed if you will have to deal with it?

I hope that I made myself clear enough.
I will really appreciate any advice. Thanks.

Best regards,
Vincent Barichard

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