A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with constraint propagation for pruning the search space. Constraint propagation is performed by propagators implementing a certain notion of consistency. Bounds consistency is the method of choice for building propagators for arithmetic constraints and several global constraints in the finite integer domain. However, there has been some confusion in the definition of bounds consistency. In this paper we clarify the differences and similarities among the three commonly used notions of bounds consistency.
reworded Lhomme @cite_15 defines which formalizes bounds propagation for both integer and real constraints. He proposes an efficient propagation algorithm implementing arc B-consistency with complexity analysis and experimental results. However, his study focuses on constraints defined by numeric relations (i.e. numeric CSPs). Lhomme @cite_15 defines which formalizes bounds propagation techniques for numeric CSPs. Unlike our definition of CSPs, constraints in numeric CSPs cannot be given extensionally and must be defined by numeric relations, which can be interpreted in either the real or the finite integer domain. Numeric CSPs also restrict the domain of variables to be a single interval.
@cite_15
1548650523
Many problems can be expressed in terms of a numeric constraint satisfaction problem over finite or continuous domains (numeric CSP). The purpose of this paper is to show that the consistency techniques that have been developed for CSPs can be adapted to numeric CSPs. Since the numeric domains are ordered the underlying idea is to handle domains only by their bounds. The semantics that have been elaborated, plus the complexity analysis and good experimental results, confirm that these techniques can be used in real applications.