Consider more complex propagator notifications (and queueing)

[Dekker1]

Background

The Propagator trait previously included a notify_event:

• The method was signalled of a change in a subscribed variable
• The method returned whether the propagator should be enqueue

The idea behind this method was that a propagator could pre-empt the different parts of the propagation algorithm it would need to activate. However, to ensure this mechanism works correctly, all changes must be signalled to the propagator.

We removed the notify_event method because most notify_event implementations simply returned true, and calling a virtual method every time seemed like a large overhead. In addition the implementation did not signal all events, but only the events until the propagator was enqueued (i.e., the method returned true). This meant that some propagation algorithms would likely be faulty when stressed.

Proposal

We can re-evaluate a new interface for notify_event that works in addition to the standard enqueueing system. My intuition says that some propagators, like AllDifferentValue, IntLinearNotEqValue, and ArrayVarIntElementBounds, might benefit from more fine-grained activation and/or partially activated propagation algorithm.

It should, however, be noted that theoretically the improvement is at most linear. The propagation algorithm could always first walk over all its variables to see what the changes are.

My plan would be to:

1. Re-introduce the Propagator::notify_event method, possibly with access to InspectionActions.
2. Introduce an additional InitializationActions::subscribe_<type> that signals to the solver which changes the notify_event method will always be called
   • This is in addition to the InitializationActions::enqueue_on_<type>_change that will always enqueue a propagator when an event happens
3. Change the engine to walk a (separate) list of subscriptions to call the notify_event method.
4. Implement the mechanism for 2 or 3 propagators to measure its effectiveness.

Evaluation: We should ensure that there to gather and run benchmarks that exercise the propagators that we intent to change and that they are merged/run before changing the propagators.