[gecode-users] Extra information during propagation
Christian Schulte
cschulte at kth.se
Wed Jan 21 10:39:22 CET 2009
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
More information about the gecode-users
mailing list