Paper Info
Title
Perfect Derived Propagators
Abstract
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also imple- ment max? Should one implement linear equations both with and with- out coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintain- ability, 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 propaga- tors are proved to be indeed perfect in that they inherit essential proper- ties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, gener- alization, specialization, and channeling are developed for several vari- able domains. We evaluate the massive impact of derived propagators. Without derived propagators, Gecode would require 140000 rather than 40000 lines of code for propagators.
Year
DOI
Venue
2008
10.1007/978-3-540-85958-1_44
Computing Research Repository
Keywords
Field
DocType
linear equation,essential property,perfectpropagator variant,perfect derived propagators,considerable effort,yields better performance,constraint variant,variable view,computer science
Discrete mathematics,Logic program,Linear equation,Computer science,Correctness,Propagator,Completeness (statistics)
Conference
Volume
ISSN
Citations 
abs/0806.1
0302-9743
3
PageRank 
References 
Authors
0.42
11
2
Name
Order
Citations
PageRank
Christian Schulte138733.89
Guido Tack237727.56