Tech Report CS-96-34

A Constraint Satisfaction Approach to a Circuit Design Problem

Jean-Francios Puget and Pascal Van Hentenryck

December 1996


A classical circuit design problem from Ebers and Moll [Ebers 54] features a system of 9 nonlinear equations in 9 variables which is very challenging both for local and global methods. This system was solved globally using an interval method by Ratschek and Rokne [Ratschek 93] in the box $[0,10]^9$ and they state:

``Our strategies are far from being perfect. They were however successful, despite enormous costs. The costs were so high that the computation for this problem is certainly not competitive, but at this time, we know no other method which has been applied to this circuit design problem and which has led to the same guaranteed result of locating exactly one solution in this huge domain, completed with a reliable error estimate. ``

This paper presents a novel branch and prune algorithm which obtains a unique safe box to the above system within reasonable computation times. The algorithm combines traditional interval techniques with an adaptation of discrete constraint satisfaction techniques to continuous problems. Of particular interest is the simplicity of the approach.

(complete text in pdf or gzipped postscript)