A Constraint Satisfaction Approach to a Circuit Design Problem.
A classical circuit-design problem from Ebers and Moll (1954) features a system of nine nonlinear equations in nine variables that is very challenging both for local and global methods. This system was solved globally using an interval method by Ratschek and Rokne (1993) in the box [0, 10]^9. Their algorithm had enormous costs (i.e., over 14 months using a network of but they state that 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. The present paper gives a novel branch-and-prune algorithm that obtains a unique safe box for 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.
Introduction
The transistor modeling problem of Ebers and Moll [6] is the system of nonlinear equations
where the constants g ik are given by
5.2095 10.0677 22.9274 20.2153
28.5132 111.8467 134.3884 211.4823
The problem is very challenging both for local and global methods because small variations in
the inputs produce large differences in the functions. Ratschek and Rokne [23] summarize various
attempts to find a solution to this problem using local methods; these descriptions are not repeated
here. It suffices to say that successful attempts require very elaborate procedures, sometimes
combining several globally convergent algorithms.
In the same paper [23], Ratschek and Rokne propose an interval method which solves the
problem globally in the box [0; 10] 9 . In particular, they show that there exists a unique solution
in this box and they provide a guaranteed error estimate by enclosing the solution in a box whose
intervals are of width smaller than 3:2 \Theta 10 \Gamma4 . The computation times to obtain this result are,
however, extremely large. No computation times were given in [23], since this was not the primary
aim of the paper. However, a preliminary draft of the paper indicated that the total process
took over 14 months using a network of workstations. Ratschek and Rokne also
recommended that such methods for solving unstable systems should be further investigated in
order to reduce the computations.
Here we present a novel interval algorithm that isolates all safe boxes (i.e., all boxes which contain
at least one solution) to nonlinear equation systems and show that the algorithm isolates a single
safe box for the circuit-design problem within reasonable computation times. 1 The main novelty
of the procedure is in the way in which constraints are used to prune the search space. The
pruning techniques, some of which were presented in [24] and some of which are novel, are based
on constraint-satisfaction techniques from artificial intelligence and are particularly effective when
far from a solution. These techniques are thus orthogonal to traditional interval techniques, which
are most effective close to a solution (when the boxes are small).
The paper is organized as follows. Section 2 gives the necessary background in interval analysis.
Section 3 discusses the problem description and the simplyfying assumptions. Section 4 presents
a generic branch-and-prune algorithm for isolating all solutions to a nonlinear system of equa-
tions, Section 5 presents the various pruning techniques, and Section 6 reconsiders the simplifying
assumptions. Section 7 reports the experimental results and Section 8 concludes the paper.
Preliminaries
Here we review some basic concepts of interval analysis to needed for this paper. More information
on interval arithmetic can be found in many places (e.g., [1, 8, 7, 17, 18, 20, 22]). Our definitions
are slightly non-standard.
2.1 Interval Arithmetic
We consider 1g, the set of real numbers extended with the two infinity symbols,
and the extension of the relation ! to this set. We also consider a finite subset F of ! 1 containing
In practice, F corresponds to the floating-point numbers used in the implementation.
is the set of real numbers
1 Proving that the safe box contains a unique solution requires some experimental trial-and-error work; see Section
6 of [23] for a discussion of this issue.
The set of intervals is denoted by I and is ordered by set inclusion. 2
S be a subset of !. The enclosure of S, denoted by S or 2S, is the
smallest interval I such that S ' I . We often write r instead of frg for r 2 !.
We denote real numbers by the letters F-numbers by the letters l; m; u, intervals by
the letter I , real functions by the letters f; g and interval functions (e.g., functions of signature
I ! I) by the letters F; G, all possibly subscripted. We use l to denote the smallest
F-number strictly greater (resp. smaller) than the F-number l. To capture outward
rounding, we use dre (resp. brc) to return the smallest (resp. largest) F-number greater (resp.
smaller) or equal to the real number r. We also use ~ I to denote a box hI and ~r to denote
a tuple hr is the set of rational numbers and N is the set of natural numbers. We also
use the following notations:
right([l;
canonical interval is an interval of the form [l; l] or [l; l
where l is a floating-point number.
The fundamental concept of interval arithmetic is the notion of interval extension.
Definition 4 [Set Extensions] Consider a set S ' ! n and a function !. The set extension
of f is defined as
I is an interval extension of
I 0 if
Example 1 The interval function \Phi defined as
is an interval extension of addition of real numbers.
In this paper, we restrict attention to monotonic interval extensions because of their fundamental
properties and because traditional interval extensions of primitive operations satisfy these requirements
naturally.
Definition 6 [Monotonic Interval Extensions] An interval function F : I n ! I is monotonic in ~
I 0
if
I 2 ' ~
I 1 ' ~
I 2
These intervals are usually called floating-point intervals in the literature.
It is important to stress that a real function can be extended in many ways. For instance, the
interval function \Phi is the most precise interval extension of addition (i.e., it returns the smallest
possible interval containing all real results), while a function always returning [\Gamma1; 1] would be
the least accurate. In the following, we assume fixed monotonic interval extensions for the primitive
operators (for instance, the interval extension of + is defined by \Phi). In addition, we overload the
real symbols and use them for their interval extensions.
2.2 Constraint Representations
It is well known that different computer representations of a real function produce different results
when evaluated with floating-point numbers on a computer. As a consequence, the way in which
constraints are written may have an impact on the behavior on the algorithm. For this reason, a
constraint or a function in this paper is considered to be an expression written in some language. In
addition, we abuse notation by denoting functions (resp. constraints) and their representations by
the same symbol. In the remaining sections, we assume that real variables in constraints are taken
from a finite (but arbitrarily large) set fx g. Similar conventions apply to interval functions
and constraints. Interval variables are taken from a finite (but arbitrarily large) set fX g.
3 Problem Description
The problem considered in this paper is finding all solutions to a system of equations
in a box ~
I
Of course, on a computer, it is generally impossible to find these solutions
exactly and interval methods aim at returning small boxes containing all solutions. Preferably,
each such box is safe, meaning that it contains a solution. For the purposes of this paper, interval
methods can thus be viewed as solving the following problem: assuming that F i is a monotonic
interval extension of f i (1 - i - n), find all canonical 3 boxes hI
I 0 satisfying
This is of course a simplification, since interval methods generally use various interval extensions.
However, restricting attention to this problem has the benefits of crystallizing the intuition underlying
our novel pruning methods. Section 6 reconsiders this simplification.
3 In practice, one may be interested in boxes of a certain width or one may want to stop as soon as a safe box is
obtained. It is easy to generalize our results to these requirements.
Notation: Let S be a system of constraints of the form
and let ~
I be a box hI We denote by S( ~
I) and S(I the fact that ~ I satisfies the
system of interval constraints S or, in symbols,
Note also that we use S to denote systems of constraints and S to denote systems of interval
constraints.
4 The Generic Branch-and-Prune Algorithm
The above problem description highlights the finite nature of the problem, since there are only
finitely many floating-point intervals. Most interval methods are thus best viewed as global search
algorithms iterating two main steps: pruning and branching. The basic schema underlying these
algorithms, the branch-and-prune schema, is depicted in Figure 1. The function Search receives a
system of interval constraints S and an initial box ~
returns the set of canonical boxes ~
I in ~
I 0
satisfying S( ~
I). The function Search first applies a pruning step that reduces the initial box. This
pruning step is the main topic of this paper. If the resulting box ~ I is empty, there is no solution to
the problem. If the box ~
I is canonical, it is returned as a result. Otherwise, the box is split along
one dimension into two subboxes, ~
I 1 and ~
I 2 , which are then explored recursively using the same
algorithm.
A specific interval algorithm can be obtained by specifying the splitting strategy and pruning
techniques. Our algorithms use a splitting strategy that consists of splitting the largest interval in
two parts. The main novelty of our algorithms lies in the pruning techniques and we will define
three pruning operators, Prune 0 , Prune 1 , and Prune 2 , that produce three distinct algorithms.
5 The Pruning Techniques
The two pruning techniques used in our algorithm are box(1)- and box(2)- consistency. To ease
understanding, these techniques are contrasted with a traditional interval technique, which we call
box(0)-consistency for reasons that will become clear below.
5.1 Box(0)-Consistency
It is traditional in branch-and-prune algorithms to use a relaxation of the problem at hand. If there
is no solution to the easier problem, it follows that there are no solutions to the original problem.
Box(0)-consistency is a weak, but very simple, relaxation used in most interval systems. Given the
function Search(S, ~
I
begin
~ I := Prune(S, ~
I 0 );
if Empty(
~
I) then
return
else if Canonical(
~
I) then
return f ~
Ig
else
I
return Search(S, ~
I 2 );

Figure

1: The Branch-and-Prune Algorithm
problem of finding canonical boxes in a box ~ I satisfying a system of interval constraints S, box(0)-
consistency consists of testing S( ~
I). If S( ~
I) does not hold, there are obviously no solutions to the
original problem, because of the definition of interval extensions. The pruning operator associated
with box(0)-consistency can thus be defined as follows:
~
I otherwise.
Box(0)-consistency can in fact be viewed as a form of projection. The original problem could be
stated as an existence question
and box(0)-consistency approximates it by replacing each interval variable by its interval to obtain
the test
which reduces to testing each constraint in S independently.
5.2 Box(1)-Consistency
This section presents the first pruning operator used in our algorithm. It starts with an informal
discussion, then specifies the pruning operator, and presents a simple implementation. 4
4 Separating the specification from the implementation has the advantage of distinguishing what is being computed
from how to compute it. There are many ways to implement the concepts described in this section, and our goal here
is to focus on the concepts, not on the technical details (which can be found elsewhere [24]).
5.2.1 Informal Presentation
The first fundamental idea underlying box(1)-consistency [2] is to project all variables but one or,
more precisely, to replace all variables but one by their intervals. This produces a stronger pruning
than box(0)-consistency but, of course, at a higher cost. The original existence problem
is thus approximated by
This relaxation can be tested relatively easily. Notice first that the conditions are independent. In
addition, a condition of the form
can be tested by considering all the canonical intervals I in I 1 and testing
Our implementation tries to be more effective by using adaptations of the interval Newton method.
The second fundamental idea underlying box(1)-consistency is to reduce the intervals associated
with the variables. Consider the relaxation
and let I l be the leftmost interval in I 1 satisfying
and I r the rightmost interval in I 1 satisfying
It should be clear that X 1 must range in the interval I 0
I
since any interval on the left or on the right of I 0 violates one of the conditions of the relaxation.
The interval associated with X 1 can thus be reduced to I 0 .
This reduction is applied for each of the variables until no more reduction takes place. The
resulting box is said to be box(1)-consistent. In the course of this process, it is possible to detect
that no solution to the original problem exists, since the intervals associated with the variables
become smaller. Note also that a variable can be considered several times in this reduction process.
5.2.2 The Pruning Operator
We now formalize the informal discussion above and present the pruning operator associated with
box(1)-consistency. Recall that all definitions assume that S is defined over the set of variables
. The main concept is box(1)-consistency, which expresses that a system cannot be
narrowed further by the reduction process described informally in the previous subsection.
Definition 7 [Box(1)-Consistency] Let S be a system of interval constraints, let ~ I be a box
n). S is box(1)-consistent in ~ I
and
S is box-consistent in ~ I if it is box(1)-consistent in ~
I wrt all i in
The pruning operator associated with box(1)-consistency simply returns the largest box in the
initial interval that is box(1)-consistent (or, more informally, the largest box in the initial interval
that cannot be narrowed further). This box always exists because of the monotonicity of interval
extensions and is unique. Of course, it can be empty.
Definition 8 [Box(1)-Consistency Pruning] Let S be a system of interval constraints and let ~
I be
a box. The pruning operator associated with box(1)-consistency can be defined as
I 0
where ~
I 0 is the largest box in ~ I such that S is box(1)-consistent in ~ I 0 .
5.2.3 A Simple Implementation
The pruning operator can be computed in many ways. Figure 2 presents a simple iterative algorithm
for this purpose; see [24] for a more efficient implementation. The algorithm is a simple fixpoint
algorithm that terminates when no further pruning can be obtained (i.e., ~
I p ). The body of the
loop applies a narrowing operation on each of the variables and produces a new box that is the
intersection of all these narrowings. The narrowing function Narrow 1 (S, ~
I,i) returns the largest
box ~
I 0 in ~
I such that S is box(1)-consistent in ~
I 0 wrt i.
5.3 Box(2)-Consistency
Box consistency has been shown to be effective for solving a variety of nonlinear applications
[24]. For some applications, however, and for the transistor modeling problem in particular, better
performance can be obtained by using a stronger local consistency condition that we call box(2)-
consistency. Box(2)-consistency is in fact an approximation of path consistency [16] and is related
to some consistency notions presented in [14].
function Prune 1 (S, ~
begin
repeat
~
I p := ~
until ~ I = ~
I
return ~ I;
function Narrow 1 (S,hI
begin
I c is canonical and S(I
return ;;
else
return

Figure

2: Implementing Box(1)-Consistency
5.3.1 Informal Presentation
Box(2)-consistency generalizes box(1)-consistency by projecting all but two variables. The original
existence problem
is thus approximated by
9X
Once again, it is possible to test this relaxation easily, at least from a conceptual standpoint. The
conditions are independent and a condition of the form
can be tested by considering all pairs of canonical intervals in I 1 and I 2 for X 1 and X 2 .
As was the case for box(1)-consistency, box(2)-consistency makes use of this relaxation to prune
the intervals associated with each variable. Consider a condition
and a canonical interval I 0
. If there is no box ~
I
such that S is box(1)-
consistent in ~ I 0 , then obviously
1 . It is thus possible to narrow the bounds of I 1 by using this
pruning rule, and this process can be iterated for all variables until no further pruning is available.
5.3.2 The Pruning Operator
The notion of box(2)-consistency is defined in terms of box(1)-consistency or, more precisely, in
terms of whether a system of interval constraints can be made box(1)-consistent in a box.
Definition 9 [Box(1)-Satisfiability] A system of interval constraints S is box(1)-satisfiable in ~
I 0 ,
denoted by BoxSat 1 (S; ~
I 0 ), if there exists a box ~
I ' ~
I 0 such that S is box(1)-consistent in ~
I.
Informally speaking, box(2)-consistency says that the bounds of each variable are box-satisfiable,
implying that they cannot be reduced further using the pruning rule described above.
S be a system of interval constraints and ~ I be a box
is box(2)-consistent in ~
I wrt i if
when l i 6= u i and if
The system S is box(2)-consistent in ~ I if it is box(2)-consistent in ~ I wrt all
It can be shown that box(2)-consistency implies box(1)-consistency.
Proposition 1 Let S be a system of monotonic interval constraints. If S is box(2)-consistent in
~
I , then S is box(1)-consistent in ~ I .
Proof Assume for simplicity that ~ I . The proof is similar
otherwise. Since S is box(2)-consistent in ~ I , S is box(2)-consistent in ~
I wrt all i (1 - i - n). Thus,
or, more explicitly,
9 ~
I
is box(1)-consistent in ~
It follows that
and, by monotonicity of F i , that
The proof that
is similar. The result follows from the definition of box(1)-consistency. 2
The pruning operator associated with box(2)-consistency simply returns the largest box in the
initial interval which is box(2)-consistent.
Definition 11 [Box(2)-Consistency Pruning] Let S be a system of interval constraints and let ~ I
be a box. The pruning operator associated with box(2)-consistency can be defined as
I 0
where ~
I 0 is the largest box in ~ I such that S is box(2)-consistent in ~ I 0 .
5.3.3 A Simple Implementation
Once again, the pruning operator can be computed in many ways. Figure 3 presents a simple
iterative algorithm close to our actual implementation. The algorithm is again a simple fixpoint
algorithm that terminates when no further pruning can be obtained. The body of the loop applies
a narrowing operation on each of the variables and produces a new box that is the intersection
of all these narrowings. The narrowing function Narrow 2 (S, ~
I,i) returns the largest box ~ I 0 in ~ I
such that S is box(2)-consistent in ~
I 0 wrt i. The pruning operator of box(1)-consistency is used to
compute this narrowing operator. Note that it would be easy to define any level of box-consistency
at this point, since box(k-1)-consistency can be used to define box(k)-consistency in a generic way.
5.4 Related Work
It is useful to relate these pruning operators to earlier work in constraint satisfaction. Projec-
tions, and approximations of projections, have been used extensively in the artificial intelligence
community (under the name consistency techniques) to solve discrete combinatorial problems (e.g.,
[16, 15]). They have been adapted to continuous problems (e.g., [5, 14]) and used inside systems
such as BNR-Prolog and CLP(BNR) [21, 3] and many systems since then. The techniques used
in systems like BNR-Prolog and CLP(BNR) are weaker than box(1)-consistency, since they
decompose all constraints into ternary constraints on distinct variables before applying a form of
box(1)-consistency. They do not scale well on difficult problems. Box(1)-consistency was introduced
in [2]. It is related to the techniques presented in [10], which uses a similar idea for the splitting
process. The consistency notions of [14] are a weaker, and less effective, form of box(k)-consistency:
it is obtained by decomposing all constraints into ternary constraints over distinct variables and by
applying a form of box(k)-consistency on the resulting constraints.
function Prune 2 (S, ~
begin
repeat
~
I p := ~
until ~ I = ~
I
return ~ I;
function Narrow 2 (S,hI
begin
I c is canonical and
return ;;
else
return

Figure

3: Implementing Box(2)-Consistency
6 The Branch-and-Prune Algorithm Revisited
We now reconsider the assumptions of Section 3. As mentioned in that section, our algorithm
uses two interval extensions, the natural interval extension and the mean value interval extension,
since distinct interval extensions may produce different prunings. In particular, the natural interval
extension is generally better when far from a solution, while the mean value interval extension is
more precise when close to a solution. This section reviews both extensions and reconsiders the
overall branch-and-prune algorithm.
6.1 The Natural Interval Extension
The simplest interval extension of a function is its natural interval extension. Informally speaking,
it consists in replacing each number by the smallest interval enclosing it, each real variable by an
interval variable and each real operation by its fixed interval extension. In the following, if f is a
real function, b
f is its natural extension.
Example 2 [Natural Interval Extension] The natural interval extension of the function x 1
is the interval function
The advantage of this extension is that it preserves how constraints are written and hence users of
the system can choose constraint representations particularly appropriate for the problem at hand.
It is useful to generalize the natural interval extension to a system of constraints.
Definition 12 [Natural Interval Extension of a System] Let S be a system of constraints
The natural extension of S, denoted by b
S, is the set of the interval constraints
The following result is easy to prove by induction.
Proposition 2 The natural interval extension of a function, a constraint, or a system of constraints
is monotonic.
6.2 The Mean Value Interval Extension
The second interval extension is based on the Taylor expansion around a point. This extension is
an example of centered forms that are interval extensions introduced by Moore [17] and have been
studied by many authors, since they have important properties. The mean value interval extension
of a function is parametrized by the intervals for the variables in the function. It also assumes that
the function has continuous partial derivatives. Given these assumptions, the key idea behind the
extension is to apply a Taylor expansion of the function around the center of the box and to bound
the rest of the series using the box.
I be a box hI be the center
of I i . The mean value interval extension of a function f in ~ I, denoted by -(f; ~
I), is the interval
function
d @f
Let S be a system of constraints
The mean value interval extension of S in ~ I , denoted by -(S; ~ I), is the system of interval constraints
function Search(S, ~
I
begin
~ I := Prune(
I 0 ), ~
I 0 );
if Empty(
~
I) then
return
else if Canonical(
~
I) then
return f ~
Ig
else
I
return Search(S, ~
I 2 );

Figure

4: The Branch-and-Prune Algorithm Revisited
Note that the mean value interval extensions is defined in terms of natural interval extensions. The
proof of the following proposition can be found in [4].
Proposition 3 The mean value interval extension of a function is a monotonic interval extension.
It is interesting to note that box consistency on the mean value interval extension of a system of
constraints is closely related to the Hansen-Sengupta operator [8], which is an improvement over
Krawczyk's operator [13]. Hansen and Smith also argue that these operators are more effective
when the interval Jacobian of the system is diagonally dominant [9] and they suggest conditioning
the system S. For the purpose of this paper, we simply assume that we have a conditioning operator
use the notation - c (S; ~ I) to denote -(cond(S; ~ I); ~
I). See [11, 12] for extensive
coverage of conditioners.
6.3 The Branch-and-Prune Algorithm
We are now in position to reconsider our branch-and-prune algorithm. The new version, given in

Figure

4, differs in two ways from the algorithm presented in Section 4. On the one hand, the
algorithm receives as input a system of constraints (instead of a system of interval constraints).
On the other hand, the operation Prune receives a system of interval constraints consisting of the
natural interval extension and the conditioned mean value interval extensions of the original system.
6.4 Existence Proof
We now describe how the algorithm proves the existence of a solution in a box. Let ff
0g be a system of equations over variables fx be a box and define the
intervals I 0
n) as follows
I 0
d
I 0
then there exists a zero in hI 0
i. A proof of this result can be found in [19].
7 Experimental Results
This section reports experimental results of the branch-and-prune algorithms. We compare the
branch-and-prune algorithm with two instantiations of the pruning operator: Prune 1 to obtain the
algorithm presented in [24] and Prune 2 to obtain a novel algorithm more effective for the transistor
modeling problem.
The Transistor Modeling Problem The box(2)-consistency algorithm was applied to find all
solutions of the transistor modeling problem. Branching was applied until a safe box or a box of
width smaller than 10 \Gamma8 was obtained. The algorithm returned a unique box
in the original range [0; 10] 9 , together with a proof that the box contains a solution. The algorithm
performs only 118 branchings and takes 2359.80 seconds (roughly 40 minutes) on a Sun Ultra-
running Solaris. This is of course a considerable improvement over the results of Ratschek
and Rokne [23]. Interestingly, the box(1)-consistency algorithm performs 135099 branchings and
takes 11841 seconds (roughly 3 hours and 20 minutes) on the same machine, still a considerable
improvement over [23].
Benchmarks from Continuation Methods It is worth comparing the box(1)- and box(2)-
consistency algorithms on some standard benchmarks from continuation methods [25]. The box(1)-
consistency algorithm compares well with continuation methods on these benchmarks [24]. Table
1 reports the results and gives, for each benchmark, the number of variables, the degree of the
polynomial system, the initial range of the variables, and the CPU time and number of branchings of
Benchmarks v d range Box(1)-Time Box(1)-Branch Box(2)-Time Box(2)-Branch
combustion
chemistry 5

Table

1: Box(1)- Versus Box(2)- Consistency on Some Benchmarks from Continuation Methods.
the box(1)- and box(2)-consistency algorithms. See [25, 24] for a description of the benchmarks. The
intention is not to compare the two algorithms systematically but rather to make readers aware that
neither of two algorithms is really superior. As can be seen, the box(2)-consistency algorithm always
performs less branchings (as should be expected) but is always slower than the box(1)-consistency
algorithm. On these problems, box(1)-consistency seems to give a better tradeoff between pruning
and pruning time. A fundamental topic for future research is thus to determine when box(2)-
consistency is more effective than box(1)-consistency and, more generally, to characterize the class
of nonlinear problems for which these techniques are effective.
8 Conclusion
This paper reconsidered the transistor modeling problem from Ebers and Moll [6], which consists
of nine nonlinear equations and is challenging both for local and global methods. The problem
was tackled by a novel branch-and-prune algorithm combining techniques from interval methods
and constraint satisfaction. In particular, the algorithm enforces a local consistency condition
called box(2)-consistency that strengthens the notion of box(1)-consistency introduced in [24]. The
algorithm was applied to find all solutions to the transistor modeling problem and returned a unique
safe box in the range [0; 10] 9 in about 40 minutes, performing only 118 branchings. The paper also
indicated that box(2)-consistency may be too strong a local condition for many problems, since it
is slower than box(1)-consistency on benchmarks from continuation methods [25]. An interesting
avenue of research is to characterize more formally the class of applications for which box(1)- and
box(2)-consistency are effective pruning techniques.

Acknowledgments

Special thanks to Christian Bliek for bringing the transistor modeling problem to our attention
and to Yves Deville for many interesting discussions. This research was partly supported by the
Office of Naval Research under grant N00014-91-J-4052 ARPA order 8225, the National Science
Foundation under grant numbers CCR-9357704, a NSF National Young Investigator Award.



--R

Introduction to Interval Computations.
CLP(Intervals) Revisited.
Applying Interval Arithmetic to Real
Mean Value Forms in Interval Analysis.
Logical Arithmetic.

An Interval Newton Method.
Bounding Solutions of Systems of Equations Using Interval Analysis.
Interval Arithmetic in Matrix Computation: Part II.
Safe Starting Regions by Fixed Points and Tightening.
Preconditioners for the Interval Gauss-Seidel Method
A Review of Preconditioners for the Interval Gauss-Seidel Method

Consistency Techniques for Numerical Constraint Satisfaction Problems.
Consistency in Networks of Relations.
Networks of Constraints
Interval Analysis.
Methods and Applications of Interval Analysis.
Safe Starting Regions for Iterative Methods.
Interval Methods for Systems of Equations.
Constraint Arithmetic on Real Intervals.
New Computer Methods for Global Optimization.
Experiments Using Interval Analysis for Solving a Circuit Design Problem.
Solving Polynomial Systems Using a Branch and Prune Approach.
Homotopies Exploiting Newton Polytopes For Solving Sparse Polynomial Systems.
--TR

--CTR
Laurent Granvilliers , Frdric Benhamou, Progress in the Solving of a Circuit Design Problem, Journal of Global Optimization, v.20 n.2, p.155-168, June 2001
Yves Deville , Micha Janssen , Pascal Van Hentenryck, Consistency Techniques in Ordinary Differential Equations, Constraints, v.7 n.3-4, p.289-315, July-October 2002
Laurent Granvilliers , Frdric Benhamou, Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.138-156, March 2006
Yahia Lebbah , Claude Michel , Michel Rueher, A Rigorous Global Filtering Algorithm for Quadratic Constraints, Constraints, v.10 n.1, p.47-65, January   2005
Yahia Lebbah , Olivier Lhomme, Accelerating filtering techniques for numeric CSPs, Artificial Intelligence, v.139 n.1, p.109-132, July 2002
Stefan Ratschan, Search Heuristics for Box Decomposition Methods, Journal of Global Optimization, v.24 n.1, p.35-49, September 2002
Frdric Benhamou , Frdric Goualard , ric Langunou, , Marc Christie, Interval constraint solving for camera control and motion planning, ACM Transactions on Computational Logic (TOCL), v.5 n.4, p.732-767, October 2004
Laurent Granvilliers , Eric Monfroy , Frdric Benhamou, Symbolic-interval cooperation in constraint programming, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.150-166, July 2001, London, Ontario, Canada
interval methods;branch and prune;constraint satisfaction;transistor modelling;electrical circuit;global zero search