P. Van Hentenryck, D. McAllester and Deepak Kapur

This paper presents Newton, a branch & prune algorithm to find
all isolated solutions of a system of polynomial constraints.
Newton can be characterized as a global search method which uses
intervals for numerical correctness and for pruning the search space
early. The pruning in Newton consists in enforcing at each node
of the search tree a unique local consistency condition, called
box-consistency, which approximates the notion of arc-consistency
well-known in artificial intelligence. Box-consistency is parametrized
by an interval extension of the constraint and can be instantiated to
produce the Hansen-Segupta's narrowing operator (used in interval
methods) as well as new operators which are more effective when the
computation is far from a solution. Newton has been evaluated
on a variety of benchmarks from kinematics, chemistry, combustion,
economics, and mechanics. On these benchmarks, it outperforms the
interval methods we are aware of and compares well with
* state-of-the-art* continuation methods. Limitations of Newton
(e.g., a sensitivity to the size of the initial intervals on some
problems) are also discussed. Of particular interest is the
mathematical and programming simplicity of the method.