Accelerating filtering techniques for numeric CSPs

✍ Scribed by Yahia Lebbah; Olivier Lhomme

• Book ID: 104105178
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 248 KB
• Volume: 139
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(02)00194-7

✦ Synopsis

Search algorithms for solving Numeric CSPs (Constraint Satisfaction Problems) make an extensive use of filtering techniques. In this paper 1 we show how those filtering techniques can be accelerated by discovering and exploiting some regularities during the filtering process. Two kinds of regularities are discussed, cyclic phenomena in the propagation queue and numeric regularities of the domains of the variables. We also present in this paper an attempt to unify numeric CSPs solving methods from two distinct communities, that of CSP in artificial intelligence, and that of interval analysis.