Christian Schulte, IMIT, KTH - Royal Institute of Technology
Speeding Up Constraint Propagation

Abstract:
This talk presents a model and implementation techniques for
speeding up constraint propagation.  Two fundamental approaches
to improving constraint propagation are explored: keeping track
of which propagators are at fixpoint, and choosing which
propagator to apply next.  We show how idempotence reasoning
and events help track fixpoints more accurately.  We improve
these methods by using them dynamically (taking into account
current domains to improve accuracy).  We define
priority-based approaches to choosing a next propagator and
show that dynamic priorities can improve propagation.  We
illustrate that the use of multiple propagators for the same
constraint can be advantageous with priorities, and introduce
staged propagators which combine the effects of multiple
propagators with priorities for greater efficiency.

  Joint work with Peter J. Stuckey, University of Melbourne