Tech Report CS-95-25

Newton: Constraint Programming over Nonlinear Real Constraints

Pascal Van Hentenryck and Laurent Michel

August 1995

Abstract:

This paper is an introduction to Newton, a constraint programming language over nonlinear real constraints. Newton originates from an effort to reconcile the declarative nature of constraint logic programming languages over intervals with advanced interval techniques developed in numerical analysis, such as the interval Newton method. Its key conceptual idea is to introduce the notion of box-consistency, which approximates arc-consistency, a notion well-known in artificial intelligence. Box-consistency achieves an effective pruning at a reasonable computation cost and generalizes some traditional interval operators. Newton has been applied to numerous applications in science and engineering, including nonlinear equation-solving, unconstrained optimization, and constrained optimization. It is competitive with continuation methods on their equation-solving benchmarks and outperforms the interval-based methods we are aware of on optimization problems.

(complete text in pdf or gzipped postscript)