APPLYING INTERVAL ARITHMETIC TO REAL, INTEGER, AND BOOLEAN CONSTRAINTS

We present in this paper a unified processing for real, integer, and B oolean constraints based on a general narrowing algorithm which applie s to any n-ary relation on R. The basic idea is to define, for every s uch relation rho, a narrowing function <(rho)over right arrow> based o n the approximation of rho by a Cartesian product of intervals whose b ounds are floating-point numbers. We then focus on nonconvex relations and establish several properties. The more important of these propert ies is applied to justify the computation of usual relations defined i n 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 mix ing numerical and Boolean values. As a result, we propose a new Constr aint Logic Programming language called CLP(BNR), where BNR stands for Booleans, Naturals, and Reals. In this language, constraints are expre ssed in a unique structure, allowing the mixing of real numbers, integ ers, and Booleans. We end with the presentation of several examples sh owing 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.