Project : coprin

Section: New Results

Keywords : constraint programming , interval analysis , symbolic-numerical calculation , numerical robustness , systems solving , constraint satisfaction problems (CSP) .

Systems solving in continuous domains

Systems solving and optimization are clearly the core of our research activities. We focus on systems solving as many applications in engineering sciences require finding all isolated solutions to systems of constraints over real numbers. It is difficult to solve as the inherent computational complexity is NP-hard and numerical issues are critical in practice. For example, it is far from being obvious to guarantee correctness and completeness as well as to ensure termination. Overall complexity of our solvers cannot be estimated in general and consequently only extensive experiments allow to estimate their practical complexity.

Our research focus on the following axis:

• developing new algorithms for local and global filtering, exclusion and existence operators. This is one of the main axis of our theoretical work. It involves numerical analysis, symbolic computation, constraints programming.

• developing specific solvers for systems sharing the same type of structure (e.g. systems of distance equations). Here also a theoretical work allows to specialize the mathematical tools we are using according to the problem at hand for a better efficiency. In parallel specific data structure are used in the implementation

• systems decomposition: the objective is to decompose large systems into sub-systems that are independent or loosely connected and are solved in sequence, allowing an important improvement of efficiency compared to general solver

• developing our generic systems solving software IcosAlias. Existing solvers exhibit lack of flexibility: our objective is to develop a framework that will allow to modify easily the solving strategy, to test new algorithms and to develop solvers for specific systems

Linearization and global filtering for numerical constraint systems

Participants : Yahia Lebbah, Claude Michel, Michel Rueher.

The purpose of our research is to introduce and to study a new branch and bound algorithm called QuadSolver. The essential feature of this algorithm is a global constraint (called Quad) that works on a tight and safe linear relaxation of the polynomial relations of the constraint systems. More precisely, QuadSolver is a branch and prune algorithm that combines Quad, local consistencies and interval methods [25] [31] [26].

QuadSolver has been evaluated on a variety of benchmarks from kinematics, mechanics and robotics. On these benchmarks, it outperforms classical interval methods as well as CSP solvers and it compares well with state-of-the-art optimization solvers.

The relaxation of nonlinear terms is adapted from the classical the ``Reformulation-Linearization Technique (RLT)'' linearization method. The simplex algorithm is used to narrow the domain of each variable with respect to the subset of the linear set of constraints generated by the relaxation process. The coefficients of these linear constraints are updated with the new values of the bounds of the domains and the process is restarted until no more significant reduction can be done. We have demonstrated that the Quad algorithm yields a more effective pruning of the domains than local consistency filtering algorithms (e.g., 2b–consistency or box–consistency). Indeed, the drawback of classical local consistencies comes from the fact that the constraints are handled independently and in a blind way. For example, when dealing with quadratic constraints, classical local consistencies do not exploit the semantic of quadratic term; for reducing the domains of the variables. Conversely, linear programming techniques do capture most of the semantics of nonlinear terms (e.g., convex and concave envelopes of these particular terms). The extension of Quad for handling any polynomial constraint system requires to replace non-quadratic terms by new variables and to add the corresponding identities to the initial constraint system. However, a complete quadrification would generate a huge number of linear constraints. We have introduced a heuristics based on a good tradeoff between a tight approximation of the non linear terms and the size of the generated constraints system.

A safe rounding process is a key issue for the Quad framework. The simplex algorithm is used to narrow the domain of each variable with respect to the subset of the linear set of constraints generated by the relaxation process but most implementations of the simplex algorithm are numerically unsafe. Moreover, the coefficients of the generated linear constraints are computed with floating point numbers. So, two problems may occur in the Quad-filtering process:

1. the whole linearization may become incorrect due to rounding errors when computing the coefficients of the generated linear constraints ;

2. some solutions may be lost when computing the bounds of the domains of the variables with the simplex algorithm.

We propose a safe procedure for computing the coefficients of the generated linear constraints. The second problem has recently been addressed by Neumaier and Shcherbina [8] which have proposed a simple and cheap procedure to get a rigorous upper bound of the objective function. The incorporation of these procedures in the Quad-filtering process allows us to call the simplex algorithm without worrying about safety.