[gecode-users] Extra information during propagation

[Vincent Barichard]

Le vendredi 23 janvier 2009 09:45:57 Christian Schulte, vous avez écrit :
> 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.
>

Ok, I will add a field to store the information I need.

> 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.

I would like to try this way too and compare with the first approach. So I 
tried to understand exactly how advisors work. I looked at the "notify" 
functions in var-imp.icc and I noticed that the "schedule" function is always 
called (except for the SUBSCRIBE event). So when the advise function of a 
propagator returns ES_FIX, the propagator is still scheduled. In the comments 
just above the "advise" function it is said that when ES_FIX is returned, the 
propagator doesn't need to be run. Is it possible for an advisor (or another 
class) to cancel the scheduling of a propagator?

Furthermore, I tried to ES_SUBSUMED a propagator within its "advise" function 
but the propagator still exists when I print the actor list of the Space. 
Nevertheless, I succeeded to ES_SUBSUMED the same propagator within its 
"propagate" function. So is it possible to ES_SUBSUMED a propagator within its 
"advise" function?

Thank you for your help, I learn every day by digging inside the code of 
GeCode :-)

>
> 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!

I like scary things :-)

Cheers,
Vincent



>
> 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

-- 
Vincent Barichard        Université d'Angers (LERIA)
Tel: 02 41 73 52 06      Département Informatique
Fax: 02 41 73 50 73      H203