[gecode-users] Why do we need to update variables for propagators

[Christian Schulte]

Hi Zoe,

 

I am not really sure that your analysis is correct: updating variables is very cheap (like initializing with a value and no more). A variable is really only a pointer to a variable implementation which is copied at most once.

 

It might be the number of propagators that is the problem and the datstructures that they use.

 

This is the crux of a copying-based solver. One has to be quite careful in how much state one keeps in a propagator. What many of Gecode’s more advanced propagators do is that they recompute the state when they are run the first time (and not when they are being cloned).

 

Cheers

Christian

 

--

Christian Schulte, www.ict.kth.se/~cschulte/

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Zhu Zichen's cse
Sent: Monday, July 13, 2015 5:40 AM
To: users at gecode.org
Subject: [gecode-users] Why do we need to update variables for propagators

 

Dear all,

 

I have some confusion on the updating of variables in the copy function of propagators. As we have updated variables in the Space when do copying, why do we still need to update them in propagators again? I think we only need to get the relation between the views that subscribed by the constraints and the variables. 

 

The reason why I propose this question is that I have implemented the propagator of a global constraint. This global constraint would occur many times during search and involves many variables. Thus the updating of variables in the copy function of its propagator would incur a large overhead. I did another version by putting all these set of same global constraints into one constraint GLOBAL_ONE and propose another propagator. This propagator works like an propagator engine but is not that efficient than the one given by Gecode (of course). Now we only need to update the entire variables once for GLOBAL_ONE. Utilizing this GLOBAL_ONE constraint wins over one-propagator-for-each constraints since the overhead of updating variables dominates the overhead of doing filtering. 

 

If we cannot avoid to update variables in the propagators, I would like to ask is it also necessary in other CSP solvers like eclipse and ILOG? If so, it would be a good research topic to find the balance between the overhead of coping and the power of filtering algorithm. 

 

Thanks for your help. 

 

Zoe

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20150714/a1f3598c/attachment.html>