The Range Constraint: Algorithms and Implementation

Abstract

We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the RANGE constraint, which computes the range of values used by a set of variables, and the ROOTS constraint, which computes the variables mapping onto particular values. In order for this specification language to be executable, propagation algorithms for the RANGE and ROOTS constraints should be developed. In this paper, we focus on the study of the RANGE constraint. We propose an efficient algorithm for propagating the RANGE constraint. We also show that decomposing global counting and occurrence constraints using RANGE is effective and efficient in practice.