Combination of Nonlinear Terms in Interval Constraint Satisfaction Techniques - Artificial Intelligence and Symbolic Computation - page 118

Combination of Nonlinear Terms
in Interval Constraint Satisfaction Techniques

Laurent Granvilliers and Mina Ouabiba

LINA, University of Nantes
2, rue de la Houssiniere, BP 92208 44322 Nantes Cedex 3, France
{ Laurent.Granvilliers,Mina.Ouabiba } @lina.univ-nantes.fr

Abstract. Nonlinear constraint systems can be solved by combining
consistency techniques and search. In this approach, the search space is
reduced using local reasoning on constraints. However, local computa-
tions may lead to slow convergences. In order to handle this problem, we
introduce a symbolic technique to combine nonlinear constraints. Such
redundant constraints are further simplified according to the precision of
interval computations. As a consequence, constraint reasoning becomes
tighter and the solving process faster. The eciency of this approach is
shown using experimental results from a prototype.

Keywords: Interval arithmetic, numerical constraint, local consistency,
symbolic algorithm, redundant constraint.

1 Introduction

The problem of solving a conjunction - a system - of nonlinear constraints over
the real numbers is uncomputable in general [3]. Only approximations may be
computed using machine numbers. Interval arithmetic [14] provides a set of op-
erations over interval numbers. In this framework, every real quantity is enclosed
by an interval. The general interval-based algorithm for solving nonlinear con-
straint systems is a bisection process. The search space, defined by the Cartesian
product of variable domains, is recursively bisected and reduced until a desired
precision is reached. Unfortunately the problem of approximating a constraint
system using interval numbers is intractable in general.
Local consistency techniques are tractable algorithms that may accelerate
the bisection algorithm [13,12]. Basically, the search space may be reduced using
constraint projections on variables. Given a variable occurring in a constraint
the projection is the set of values that may be assigned to the variable such
that the constraint can be satisfied. These values are said to be consistent. It
follows that the complementary set (the inconsistent values) can be removed
from the variable domain. Such domain reductions have to be iterated until

This work has been partially supported by a 2003-04 Procope project funded by
the French Ministry of Education, the French Ministry of Foreign Affairs, and the
German Academic Exchange Service (DAAD).