Towards "Propagation = Logic + Control"

Constraint propagation algorithms implement logical infe r-ence. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level fra mework that clearly differentiates between information needed for cont rolling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriaten ess of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algo rithms, such as literal watching for unit clause propagation and the lexi cographic ordering constraint. We provide an implementation and benchm ark results that demonstrate the practicality and efficiency of our frame work.