Schedulers and Redundancy for a Class of Constraint Propagation Rules
Title: Schedulers and Redundancy for a Class of Constraint Propagation Rules
Abstract: This research study focuses on developing efficient schedulers for a specific class of rules called propagation rules, which naturally arise in the context of rule-based constraint programming. The authors introduce an abstract framework for scheduling and instantiate it with specific partial orderings and functions to obtain a scheduler called R. They demonstrate the effectiveness of this approach by implementing it for membership rules, a particular type of propagation rule. The implementation significantly outperforms the standard implementation of membership rules in the CHR language, providing practical benefits from studying the constraint propagation process on an abstract level. Additionally, the research clarifies how to identify redundant propagation rules and compute appropriately reduced sets of rules.
Main Research Question: How can we develop efficient schedulers for a class of constraint propagation rules to improve the performance of constraint programming?
Methodology: The authors use a generic iteration algorithm on partial orderings to develop an abstract framework for scheduling. They instantiate this framework with specific partial orderings and functions to obtain the R algorithm, a scheduler for propagation rules. They implement this scheduler for membership rules, a specific type of propagation rule.
Results: The implementation of the R algorithm outperforms the standard implementation of membership rules in the CHR language, demonstrating a significant improvement in performance.
Implications: This research has practical benefits for the field of constraint programming. By studying the constraint propagation process on an abstract level and developing efficient schedulers, it is possible to improve the performance of constraint programming systems. Additionally, the research provides insights into identifying and reducing redundant rules, which can further enhance the efficiency of these systems.
Link to Article: https://arxiv.org/abs/0403037v2 Authors: arXiv ID: 0403037v2