2008/06/11 by Christian Schulte, Schulte, Christian, Guido Tack +1 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #D.3.2 #D.3.3 #FOS: Computer and information sciences #Model-Driven Software Engineering Techniques #cs.AI
paper · pdf · doi:10.48550/arxiv.0806.1806
17 pages, 2 tables
arxiv created 2008/06/11 · openalex publication_date 2008/06/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance. This paper shows how to use variable views, previously introduced for an implementation architecture, to derive perfect propagator variants. A model for views and derived propagators is introduced. Derived propagators are proved to be indeed perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and channeling are developed for several variable domains. We evaluate the massive impact of derived propagators. Without derived propagators, Gecode would require 140000 rather than 40000 lines of code for propagators.