Towards "Propagation = Logic + Control"

Brand, Sebastian and Yap, Roland H.C. (2006) Towards "Propagation = Logic + Control". [SICS Report]



Constraint propagation algorithms implement logical inference. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level framework that clearly differentiates between information needed for controlling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriateness of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algorithms, such as literal watching for unit clause propagation and the lexicographic ordering constraint. We provide an implementation and benchmark results that demonstrate the practicality and efficiency of our framework.

Item Type:SICS Report
Uncontrolled Keywords:constraint programming, constraint logic programming, constraint propagation
ID Code:2305
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:05

Repository Staff Only: item control page