RealPaver is an interval software for modeling and solving nonlinear systems. Reliable approximations of continuous or discrete solution sets are computed using Cartesian products of intervals. Systems are given by sets of equations or inequality constraints over integer and real variables. Moreover, they may have different natures, being square or nonsquare, sparse or dense, linear, polynomial, or involving transcendental functions.The modeling language permits stating constraint models and tuning parameters of solving algorithms which efficiently combine interval methods and constraint satisfaction techniques. Several consistency techniques (box, hull, and 3B) are implemented. The distribution includes C sources, executables for different machine architectures, documentation, and benchmarks. The portability is ensured by the GNU C compiler.

Many problems in robust control and motion planning can be reduced to either finding a sound approximation of the solution space determined by a set of nonlinear inequalities, or to the "guaranteed tuning problem" as defined by Jaulin and Walter, which amounts to finding a value for some tuning parameter such that a set of inequalities be verified for all the possible values of some perturbation vector. A classical approach to solving these problems, which satisfies the strong soundness requirement, involves some quantifier elimination procedure such as Collins' Cylindrical Algebraic Decomposition symbolic method. Sound numerical methods using interval arithmetic and local consistency enforcement to prune the search space are presented in this article as much faster alternatives for both soundly solving systems of nonlinear inequalities, and addressing the guaranteed tuning problem whenever the perturbation vector has dimension 1. The use of these methods in camera control is investigated, and experiments with the prototype of a declarative modeler to express camera motion using a cinematic language are reported and commented upon.

This paper surveys the field of cooperative constraint solving for a constraint programming perspective with an emphasis on combinations of symbolic and interval methods. On the one hand, symbolic methods provide adapted representations of the constraint expressions. On the other hand, interval methods compute verified enclosures of solution sets. Using cooperation of solvers, one can take advantage of both techniques in a unified framework: symbolic algorithms generally need to be combined with root extraction methods, and the efficiency of interval algorithms strongly depends on constraint expressions.

We study the properties of monotonic parts of (continuous) constraints. We design a general framework to reason about them : directions can be abstracted by signs, which capture significant information on the location of solutions. We show that this formalism is appropriate to study the relative position of solution sets. Efficient algorithms are proposed to diagnose the behaviour of some consistency techniques. These methods raise new perspectives on an open issue: the prediction of the consistency technique to be used wrt a given problem.

Interval constraint solvers use local consistencies-among which one worth mentioning is box consistency-for computing verified solutions of real constraint systems. Though among the most efficient ones, the algorithm for enforcing box consistency suffers from the use of time-consuming operators. This paper first introduces box/sub /spl phi// consistency, a weakening of box consistency; this new notion then allows us to devise an adaptive algorithm that computes box consistency by enforcing box/sub /spl phi// consistency, decreasing the /spl phi/ parameter as variables' domains get tightened, then achieving eventually box/sub 0/ consistency, which is equivalent to box consistency. A new propagation algorithm is also given, that intensifies the use of the most contracting pruning functions based on box/spl phi/ consistency. The resulting algorithm is finally shown to outperform the original scheme for enforcing box consistency on a set of standard benchmarks.

Constraint programming is an emerging technology that offers an original approach allowing for efficient and flexible solving of complex problems. Its main advantage relies in its ability to compute with partial information expressed in terms of constraints. These constraints are monotonically, accumulated during the program execution in order to restrict the problem search space. We address one of the cornerstones of this technology, namely the current lack of debugging facilities. In particular visualization and understanding of the underlying constraint system during program executions is very important. We propose to structure this huge, flat and intricate part of the execution data in order to provide access to high level examination of its evolution. More precisely, we present a means to hierarchically organize sets of constraints in order to divide them into manageable parts while presenting computation correctness. Soundness of our method is shown, an algorithm supporting it is given, and an implemented prototype exhibiting its effectiveness is described.