[gecode-users] question about view types and propagator templates

Guido Tack tack at ps.uni-sb.de
Fri Jan 9 08:17:02 CET 2009

Denys Duchier wrote:

> Guido Tack <tack at ps.uni-sb.de> writes:
>> Denys Duchier wrote:
>>> Also:
>>> is there a downside to providing the most general templates?
>> There is actually a downside (although it's not the reason we didn't
>> provide the templates).  If you use the ModEventDelta during
>> propagation, you have to access it through all the view types of the
>> propagator and combine the results.  The more types you allow, the
>> less accurate is the ModEventDelta.  E.g., if you get ME_SET_GLB, but
>> you use one SetView and one ComplementView, the combined delta is
>> ME_SET_BB (and you have to compute the combined ModEventDelta  
>> yourself).
> I think that was the sound of your explanation, as it quickly flew  
> above
> my head ;-)

Look at gecode/set/rel/eq.hpp:94.  The Eq propagator has two views,  
and its propagate method gets the ModEventDelta med, which describes  
the cumulated modifications (on all subscribed variables) since the  
last invocation.  Now assume the lower bounds of the two subscribed  
variables x and y have been modified.  Then med is ME_SET_GLB.  So the  
propagator knows that it just has to perform the lower bound  
reasoning, it can skip the other inferences.  That's what's determined  
by the testSetEventLB etc functions.

Now if Eq is instantiated with a SetView on x and a ComplementView on  
y, it still gets ME_SET_GLB as the med (because the kernel doesn't  
know about the views).  So Eq asks the views to translate the med (in  
lines 96 and 97).  The SetView just returns ME_SET_GLB, and the  
ComplementView returns ME_SET_LUB (because a glb change in y  
corresponds to a lub change in its complement).  So we'll have to do  
lub reasoning as well.

Now assume that only the glb of x has changed.  Still, the med must be  
converted through both views (we don't know which of the two views has  
the changed domain), and we'll have to run the lub propagation  
although it won't contribute any pruning.


More information about the gecode-users mailing list