Advisor (delta) exact information for value prune

[John]

Hello, I would like to ask about the delta information in advisors, when programming custom propagators. From what I understand by reading the documentation, when a value gets pruned from a variable, in the general case we cannot know which value it is. So if we need this information in order to update our internal representation of the constraint accordingly within the propagator, we need to scan all the values currently in the domain of the view that changed, and compare them with the ones in our internal representation, to find the exact value that got pruned, which doesn't sound very efficient. Is this the approach that common efficient Gecode built-in constraints use, or is there a trick or something that I am missing?

Thank you!

[Mikael Zayenz Lagerkvist]

Hi,

While it would in principle be possible to give the exact delta on all
changes, this would introduce a very large and unacceptable overhead
for all propagators on all domain modifications, slowing down the
system significantly. As a compromise, Gecode supplies a conservative
estimate when possible of the change, and otherwise just notes that
something has changed. Note that it is not uncommon for a reasonable
delta to be given; most domain changes in my experience are fairly
simple (change the bounds, remove a single value) and can be supplied.

We've found that this gives a reasonable balance. In most cases, just
the identity of the changed variable is enough to support an improved
propagator. In other cases where more detailed information is needed,
the advisor can use the information if it is available. For a full
example of this, the advisor for the extensional constraint with
layered graphs (aka the regular constraint), the implementation does
different things depending on if a value has been removed, a range has
been removed, or if something has changed:
https://github.com/Gecode/gecode/blob/6b09bea4863e32d00c1bdbeb2e2be36fdfe4fcf7/gecode/int/extensional/layered-graph.hpp#L475

As an alternative it could similarly be reasonable to just note in the
propagator that a full propagation is needed when the delta is
unknown. In that way, delta information is used when possible and for
other cases the updates are delayed.

Hope this helps,
Mikael

> --
> You received this message because you are subscribed to the Google Groups "Gecode" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to gecode+un...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/gecode/3dcd81a9-36f4-477e-b9f3-878f08d7f031n%40googlegroups.com.



--
Mikael Zayenz Lagerkvist