Implementing Efficient Propagation Control
Christian Schulte, Guido Tack.
In propagation-based constraint solvers, propagators implement constraints by removing inconsistent values from variable domains. To make propagation efficient, modern constraint solvers employ two mechanisms of propagation control, event-based and prioritized propagation. Events, such as a bounds change of a particular variable, control which propagators need to be scheduled for re-evaluation. Prioritization controls which of the scheduled propagators is executed next.
While it has been shown that the combination of event-based and priority-based scheduling is an efficient approach for propagation control, this is the first publication on the implementation details of such a system.
This paper presents the design of efficient data structures for propagator priority queues and the event system. The paper introduces the notions of modification events and propagation conditions, which refine the event-based model of propagation and yield an efficient implementation. The presented architecture is the basis of Gecode.
In: Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a conference workshop of CP 2010, St Andrews, UK. September, 2010.