Applying interval arithmetic to real, integer, and Boolean constraints

We present in this paper a unified processing for real, integer, and Boolean constraints based on a general narrowing algorithm which applies to any n-ary relation on R. The basic idea is to define, for every such relation rho, a narrowing function <(rho)over right arrow> based on the approximation of rho by a Cartesian product of intervals whose bounds are floating-point numbers. We then focus on nonconvex relations and establish several properties. The more important of these properties is applied to justify the computation of usual relations defined in terms of intersections of simpler relations. We extend the scope of the narrowing algorithm used in the language BNR-Prolog to integer and disequality constraints, to Boolean constraints, and to relations mixing numerical and Boolean values. As a result, we propose a new Constraint Logic Programming language called CLP(BNR), where BNR stands for Booleans, Naturals, and Reals. In this language, constraints are expressed in a unique structure, allowing the mixing of real numbers, integers, and Booleans. We end with the presentation of several examples showing the advantages of such an approach from the point of view of the expressiveness, and give some preliminary computational results from a prototype. (C) Elsevier Science Inc., 1997.