[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).
>
> WOOSH!
>
> 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.
Cheers,
Guido
More information about the gecode-users
mailing list