[gecode-users] BDD-based propagator for Gecode

[Mikael Zayenz Lagerkvist]

Hi,

There are two principal ways to find out what variables have been
changed. The first is to iterate through all the variables, and to
check if they have changed (for example, by comparing the size with a
cache of the previous size), or by using advisors. You can replace
subscriptions with advisors to know exactly which variable has been
modified. For information about the concept see [1], for some examples
see the Layered graph and Boolean linear equation propagators, and for
some practical information see previous discussion in the mailing list
[2]

Apart from this, I wonder if the search for the modified variables
really is the prime source of inefficiency. Testing the variables is
constant time (and thus linear in the number of variable to test all
variables), while computing the valid domains is linear in the size of
the BDD.

Cheers/
Mikael

PS. In general, a propagator stores views and not variables, so I'm
not sure why you need to create a view for each variable.

[1] http://www.gecode.org/paper.html?id=LagerkvistSchulte:CP:2007
[2] http://search.gmane.org/search.php?group=gmane.comp.lib.gecode.user&query=advisor


On Thu, Dec 11, 2008 at 1:24 PM, Anden blah <anden_blah at hotmail.com> wrote:
>
> Hi
>
> I am developing a BDD-based propagator for Gecode, and I have difficulty making it fast enough to be useful. Basically what I am doing is to subscribe to PC_GEN_ASSIGNED events on each of the variables involved in the BDD. Then when propagate is being called I find out which variable has been assigned, restrict the BDD accordingly and find the new valid domains (according to the BDD) so that I can prune values from the domain store.
>
> One of the issues I have is that I do not know which variable that has had a value assigned to it when propagate is being called. To solve this I am currently iterating through each of the variables involved in the BDD that have not been assigned so far, create a view on each of them and call the method assigned() to find the variable. This however is inefficient and I wonder if I can get this information in a better way (?)
>
> If you have any good suggestions, advice or resources regarding bdd propagators for Gecode it would be greatly appreciated.
>
> Thanks
>
> Andreas
>
> ________________________________
> Get news, entertainment and everything you care about at Live.com. Check it out!
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/