Project : coprin

Section: Scientific Foundations

Scientific Foundations

The scientific objective of the COPRIN project is to develop and implement systems solving algorithms based on constraints propagation methods, interval analysis and symbolic computation, with interval arithmetics as the primary tool.

The results obtained with these algorithms are certified in the sense that all solutions will be obtained and can be calculated with an arbitrary accuracy. Furthermore some of our algorithms will allow us to deal with systems involving uncertain coefficients.

A system will be constituted by a set of relations that may use all the usual mathematical operators and functions (hence we may deal, for example, with the relation $sin(x+y)+log(cos(e^x)+y2)\le 0$ ).

We are interested in real-valued constraint satisfaction problems (( $f\left(X\right)=0$ , $f\left(X\right)\le 0$ )), in optimization problems and in the proof of the existence of properties (for example it exists X such that $f\left(X\right)=0$ or it exists two values $X_1$ , $X_2$ such that $f(X_1)>0$ and $f(X_2)<0$ )

Solutions will be searched within a finite domain (called a box) which may be either continuous or mixed (i.e. for which some variables must belong to a continuous range while other variables may only have value within a discrete set). An important point is that we aim to find all the solutions within the domain as soon as the computer arithmetics will allow it: in other words we are looking for certified solutions.

Our approach is to develop various operators that will be applied in sequence on a box:

1. exclusion operators: these operators determine that there is no solution to the problem within a given box

2. contractors: these operators may reduce the size of the box i.e. decrease the width of the allowed ranges for the variables

3. existence operators: they allow one to determine that there is a unique solution within a given box and are usually associated to a numerical scheme that enables to compute this solution in a safe way

If a given box is not rejected by the exclusion operators and is not modified by the other operators, then we will bisect one of the variables in order to create two new boxes that will be processed later on. Methods for choosing the bisected variable are also clearly within the scope of the project.

Our research aims to develop operators that can be used for any problem or are specific to a given class of problem, especially problems that are issued from application domains for which we have internally an expertise (such as mechanism theory and software engineering). Furthermore we will study symbolic computation based methods:

• to develop a user-friendly interface that will automatically generate an executable program, run it and return the result to the interface

• to analyze the semantics and syntax of the relations involved in a problem in order to generate automatically specific operators or to obtain a better interval evaluation of the relations (as interval arithmetics is very sensitive to the relations syntax)

• to allow for the calculation of the solution with an arbitrary accuracy: certified interval solution will be obtained through a compiled program which is much more efficient than its symbolic computation equivalent and then a symbolic computation procedure will be used to calculate the solution up to the desired accuracy