[gecode-users] Extra information during propagation
cschulte at kth.se
Wed Jan 21 10:39:22 CET 2009
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
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 Schulte, www.ict.kth.se/~cschulte/
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
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
domains of a,c,d:
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
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
I think about two ways of doing this :
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'.
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 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
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
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
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.
Gecode users mailing list
users at gecode.org
More information about the gecode-users