Tech Report CS-95-01

Solving Polynomial Systems Using a Branch and Prune Approach

P. Van Hentenryck, D. McAllester, and D. Kapur

February 1995

Abstract:

This paper presents Newton, a branch \& prune algorithm to find all isolated solutions of a system of polynomial constraints. {\tt 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 Hansen-Segupta 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.

(complete text in pdf or gzipped postscript)