=Paper=
{{Paper
|id=Vol-2396/paper3
|storemode=property
|title=Simple and Effective Sign Consistency Using Interval Arithmetic
|pdfUrl=https://ceur-ws.org/Vol-2396/paper3.pdf
|volume=Vol-2396
|authors=Federico Bergenti,Stefania Monica
|dblpUrl=https://dblp.org/rec/conf/cilc/BergentiM19
}}
==Simple and Effective Sign Consistency Using Interval Arithmetic==
https://ceur-ws.org/Vol-2396/paper3.pdf
Simple and Effective Sign Consistency
Using Interval Arithmetic
Federico Bergenti and Stefania Monica
Dipartimento di Scienze Matematiche, Fisiche e Informatiche
Università degli Studi di Parma, 43124 Parma, Italy
{federico.bergenti,stefania.monica}@unipr.it
Abstract. Polynomial constraints over finite domains are expressed as
equalities, inequalities, and disequalities of polynomials with integer co-
efficients whose variables take values from finite subsets of the integers.
They are an interesting type of constraints that can be used to model
many combinatorial problems over the integers. Sign consistency is a
type of local consistency proposed specifically to support reasoning on
polynomial constraints over finite domains. Sign consistency is parame-
terized in terms of a bounding function that is used to extract relevant
information from a constraint when its variables are restricted to take
values from a finite box. Known results from the literature on interval
arithmetic can be readily used to propose a simple bounding function
to support sign consistency. Preliminary experimental results show that
the proposed bounding function is a promising candidate to effectively
reason on polynomial constraints over finite domains.
Keywords: Sign consistency · Bounding functions · Polynomial con-
straints over finite domains · Constraint satisfaction problems.
1 Introduction
Polynomials are ubiquitous because they are the basis of important applications
in virtually all fields of science and engineering. In addition, the influential litera-
ture on computer algebra witnesses the advanced level of understanding of poly-
nomials from a computational point of view (e.g., [11]). Polynomial constraints,
which are commonly regarded as constraints expressed in terms of equalities
and inequalities of polynomials whose variables take values from subsets of the
reals, are studied extensively in constraint satisfaction (e.g., [17]) and in con-
strained optimization (e.g., [18]). Polynomial constraints over finite domains [2]
are polynomial constraints whose variables are restricted to take values from
finite subsets of the integers. As such, they extend polynomial constraints with
the addition of disequalities, which are not normally considered for real vari-
ables. Polynomial constraints over finite domains have been initially studied in
the scope of constraint logic programming [2,4,5,6], but this paper shows that
they can also be studied in the scope of constraint satisfaction problems, as
anticipated in a previous preliminary work [3].
Sign consistency is defined and studied in an upcoming paper as a type
of local consistency (e.g., [17]) specifically designed to take advantage of the
peculiarities of polynomial constraints over finite domains. Sign consistency is
parameterized in terms of a bounding function whose purpose is to extract rele-
vant information from a given constraint when its variables are restricted to take
values from a given box. Bounding functions are used to adapt sign consistency
to the characteristics of studied problems, and to compromise its strength with
the computational cost needed to enforce it. The definition of sign consistency
is briefly reported in Section 4, and interested readers can obtain from authors
a preprint of the paper where sign consistency is comprehensively studied. Rel-
evant characteristics of sign consistency, which include its intimate relationship
with hyper-arc consistency (e.g., [1]), are discussed in the mentioned paper.
Polynomial constraints over finite domains are expressed as equalities, in-
equalities, and disequalities of polynomials whose variables take values from fi-
nite subsets of the integers. Therefore, the satisfiability of one of such constraints
can be studied in terms of the study of the sign of a polynomial function. Sign
consistency uses this approach to reason on polynomial constraints over finite
domains. In particular, sign consistency delegates the study of the sign of poly-
nomial functions to a bounding function that is chosen to adapt it to the char-
acteristics of the studied problem. The chosen bounding function is expected to
provide effective lower and upper bounds of studied polynomial functions when
their variables take values from given boxes.
Various bounding functions with diverse characteristics can be readily de-
fined. A very simple bounding function can be defined in terms of the exhaustive
enumeration of the elements of the given box, which is always finite because the
variables of studied constraints take values from finite subsets of the integers.
Such a bounding function is obviously impractical even for moderately complex
problems. A less trivial bounding function can be defined using classic results
on the Bernstein form of polynomials (e.g., [7] for a survey of recent results and
a historical retrospective). The use of such a bounding function is expected to
be applicable in practical situations only if advanced algorithms to compute the
Bernstein form of polynomials are adopted (e.g., [8,10,13,14,20]). Finally, a third
bounding function can be defined on the basis of a generalization for several vari-
ables [3] of known results for one [16] and two [9] real variables whose values are
restricted to the closed interval [0, 1]. The computational cost associated with
such a bounding function is expected to be lower than that of the other two
mentioned alternatives because it evaluates the given polynomial function only
at the corners of the considered box.
Even if mentioned bounding functions can be used to support sign consistency
with no restrictions on the considered constraints or on the considered domains
of variables, preliminary results suggest that their inherent computational cost
is not compatible with practical problems. For this reason, this paper proposes a
simple bounding function whose purpose is to make sign consistency a valuable
tool to solve practical constraint satisfaction problems that include polynomial
constraints over finite domains.
As discussed in Section 4, the bounding function proposed in this paper is
based on classic results from the literature on interval arithmetic (e.g., [21]). The
lower and upper bounds computed using such a bounding function are expected
to be less stringent than those computed using one of the three bounding func-
tions mentioned above, but its simplicity and low computational cost contribute
to make it a viable option for practical problems. Preliminary experimental re-
sults on the use of the proposed bounding function to solve a few selected con-
straint satisfaction problems taken from a well-known library of problems are
presented in Section 5. In detail, a prototype implementation of a specific al-
gorithm to solve constraint satisfaction problems using the proposed bounding
function was included in PolyFD, which is an experimental C++ library for
constraint satisfaction. Then, specific programs that take advantage of PolyFD
were used to solve the selected problems and to gather preliminary experimental
results. Obtained experimental results are encouraging because they show that
the time needed to solve studied problems using PolyFD is within the same order
of magnitude of the time needed to solve the same problems using Gecode [19].
This paper is organized as follows. Section 2 provides a self-contained presen-
tation of adopted notation, which includes the notation borrowed from interval
arithmetic. Section 3 presents polynomial constraints over finite domains in the
scope of constraint satisfaction problems. Section 4 introduces sign consistency
and discusses the proposed bounding function. Section 5 shows preliminary ex-
perimental results on the use of the proposed bounding function to solve a few
selected constraint satisfaction problems. Finally, Section 6 concludes the paper
and provides a brief overview of future research directions.
2 Notation and Preliminaries
This section is intended to provide a self-contained report on adopted notation.
The adopted notation is based on the ordinary notation used to study polyno-
mial functions of several variables, and it includes the characteristic notation of
interval arithmetic. Note that, together with the common notation used to study
polynomial functions of real variables, a specific notation is also introduced to
study polynomial functions with integer coefficients whose variables take values
from finite subsets of the integers.
The set of natural numbers, which includes zero, is denoted as N, while the
set of positive natural numbers is denoted as N+ . Given n ∈ N+ , a multi-index
I ∈ Nn is defined as an n−tuple of natural numbers
I = (i1 , i2 , . . . , in ) = (ik )nk=1 , (1)
where the common notation of using an uppercase letter to denote a multi-index,
and the same letter, but lowercase and with a subscript, for its components is
used. The following notation is adopted to use a multi-index I ∈ Nn as an
exponent for t ∈ Rn with t = (t1 , t2 , . . . , tn ) = (tk )nk=1
n
Y
tI = tikk , (2)
k=1
where the common notation of using a boldface letter to denote an n−tuple of
real numbers, and the same letter, but lightface and with a subscript, for its
components is used. Note that the common understanding of 00 = 1 is adopted
consistently in this paper.
Given two multi-indices I ∈ Nn and J ∈ Nn , they can be compared using the
following partial order
I ≤ J ⇐⇒ i1 ≤ j1 ∧ i2 ≤ j2 ∧ · · · ∧ in ≤ jn (3)
and they can be added componentwise
I + J = (i1 + j1 , i2 + j2 , . . . , in + jn ). (4)
The following abbreviation is introduced for multi-indices H ∈ Nn , I ∈ Nn , and
J ∈ Nn to express repeated sums
X j1
X j2
X jn
X
(·) = ··· (·). (5)
H≤I≤J i1 =h1 i2 =h2 in =hn
Note that H is omitted in (5), so that only I ≤ J remains, if it is the null
multi-index (0)nk=1 .
Using the multi-index notation, a polynomial function p : Rn 7→ R of n ∈ N+
real variables with real coefficients can be expressed as
X
p(x) = aI xI , (6)
I≤L
where {aI }I≤L ⊂ R is the set of the coefficients of p, and multi-index L ∈ Nn
is the multi-degree of p. The vector space of polynomial functions of n ∈ N+
real variables, with real coefficients, and with multi-degree less than or equal to
multi-index L ∈ Nn is
ΠL = spanR {PI }I≤L PI : Rn 7→ R PI (x) = xI . (7)
Similarly, a polynomial function p̃ : Zn 7→ Z of n ∈ N+ integer variables with
integer coefficients can be expressed as
X
p̃(x) = ãI xI , (8)
I≤L
where {ãI }I≤L ⊂ Z is the set of the coefficients of p̃, and multi-index L ∈ Nn
is the multi-degree of p̃. The vector space of polynomial functions of n ∈ N+
integer variables, with integer coefficients, and with multi-degree less than or
equal to multi-index L ∈ Nn is
Π̃L = spanZ {P̃I }I≤L P̃I : Zn 7→ Z P̃I (x) = xI . (9)
Given that the major interest in this paper is on the study of the bounds of
polynomial functions over boxes, the following notation for intervals and boxes
is recalled. A closed (real) interval from a ∈ R to a ∈ R is denoted as
[a, a] = {x ∈ R : a ≤ x ≤ a}, (10)
and it equals the empty set if and only if a > a. A singleton (real) interval that
contains only a ∈ R is denoted as [a] = [a, a]. Given n ∈ N+ , a (real) box B ⊂ Rn
from b = (bk )nk=1 ∈ Rn to b = (bk )nk=1 ∈ Rn is denoted as
B = [b, b] = [b1 , b1 ] × [b2 , b2 ] × · · · × [bn , bn ], (11)
and it equals the empty set if and only if bi > bi for some 1 ≤ i ≤ n. Note
that the notation Bi = [bi , bi ] ⊂ R with 1 ≤ i ≤ n is used to refer to the closed
intervals that compose the nonempty box B. Also note that the notation Bi→S
is used to refer to the box obtained by replacing the i−th closed interval that
composes the nonempty box B with the nonempty closed interval S ⊂ R.
The notation just recalled for intervals and boxes is often adapted to refer
to integer intervals and integer boxes, as follows. An integer interval from c ∈ Z
to c ∈ Z is denoted as
[c..c] = {x ∈ Z : c ≤ x ≤ c}, (12)
and it equals the empty set if and only if c > c. A singleton integer interval that
contains only c ∈ Z is denoted as [c] = [c..c]. Given n ∈ N+ , an integer box
D ⊂ Zn from d = (dk )nk=1 ∈ Zn to d = (dk )nk=1 ∈ Zn is denoted as
D = [d..d] = [d1 ..d1 ] × [d2 ..d2 ] × · · · × [dn ..dn ], (13)
and it equals the empty set if and only if di > di for some 1 ≤ i ≤ n. Note that
the notation Di = [di ..di ] ⊂ Z with 1 ≤ i ≤ n is used to refer to the integer
intervals that compose the nonempty box D. Also note that the notation Di→T
is used to refer to the box obtained by replacing the i−th integer interval that
composes D with the nonempty integer interval T ⊂ Z. Finally, the bounding
box A of a nonempty finite integer set A ⊂ Zn is the inclusion-minimal integer
box such that A ⊆ A.
Interval arithmetic (e.g., [21]) uses the introduced notation to express com-
putations whose arguments and results are closed intervals. In particular, arith-
metic operations on nonempty closed intervals are normally defined in interval
arithmetic as follows. Given two nonempty closed intervals A = [a, a] ⊂ R and
C = [c, c] ⊂ R, they can be added
A + C = [a + c, a + c], (14)
and they can be multiplied
A · C = [min{a c, a c, a c, a c}, max{a c, a c, a c, a c}]. (15)
In both cases, the result is a nonempty closed interval. Note that the product
among intervals can be used to define the m−th power of a closed interval A ⊂ R,
where m ∈ N+ . Also note that the convention [0]0 = [1] is adopted consistently
in this paper. Given n ∈ N+ , a nonempty box B ⊂ Rn , and a multi-index I ∈ Nn ,
the following notation that uses only products among intervals is adopted
n
i
Y
BI = Bj j . (16)
j=1
Using the introduced notation, which is borrowed from interval arithmetic, a
polynomial function p : Rn 7→ R of n ∈ N+ real variables with real coefficients
can be extended to work on boxes. If polynomial p is expressed as in (6), then
for any box B ⊂ Rn X
p(B) = [aI ]B I , (17)
I≤L
where the notation for singleton intervals is used to treat the coefficients of the
polynomial function as closed intervals. Note that it is easy to prove that the
result of the evaluation of p(B) is a closed interval that includes the range of
p over box B, which ensures that interval arithmetic can be used to perform
validated computations (e.g., [21]).
Even if interval arithmetic is not normally used to express computations on
integer intervals, the introduced notation can be easily generalized to integer
intervals and integer boxes. Actually, straightforward generalizations to integer
intervals of the arithmetic operations on closed intervals defined previously can
be used to express the evaluation of a polynomial function p̃ of n ∈ N+ integer
variables with integer coefficients when an integer box D ⊂ Zn is used as argu-
ment. The result of such an evaluation is an integer interval that includes the
range of p̃ over the integer box D.
3 Polynomial Constraints over Finite Domains
This section presents polynomial constraints over finite domains in the scope of
constraint satisfaction problems. Note that polynomial constraints over finite do-
mains have been already studied in the scope of constraint logic programming in
previous papers [2,4,5,6]. The discussion in this section differs from the presenta-
tions in cited papers mostly because polynomial constraints over finite domains
are presented in cited papers using a canonical form that is not adopted in this
paper. Actually, in order to simplify the presentation, the canonical form adopted
in cited papers expresses constraints using only inequalities, which ultimately re-
quires to increase the multi-degrees of polynomials to treat disequalities. In this
paper, a different form of constraints is used to avoid increasing the multi-degrees
of polynomials. Note that the form of constraints adopted in this paper is still
questionable because it requires to increase the number of constraints to treat
equalities. In addition, note that the adopted form of constraints is not required
to be unique, and therefore it is not canonical.
The following ordinary nomenclature on constraint satisfaction problems
(e.g., [1]) is needed to formally introduce polynomial constraints over finite do-
mains in Definition 2.
Definition 1 (Constraint, assignment, and satisfiability). An n−ary con-
straint C whose n ∈ N+ variables take values from domains (Di )ni=1 is a subset
of the Cartesian product of the domains of variables
n
Y
C⊆ Di . (18)
i=1
An assignment a of the variables of C is an element of the Cartesian product of
the domains of variables
Yn
a∈ Di . (19)
i=1
An assignment of the variables of C satisfies C if and only if a ∈ C. A constraint
C is satisfiable if there exists at least one assignment of its variables that satisfies
the constraint (i.e., C 6= ∅). On the contrary, a constraint C is unsatisfiable if
no such an assignment exists (i.e., C = ∅).
The following definition captures the informal statement that describes poly-
nomial constraints over finite domains as constraints expressed as equalities, in-
equalities, and disequalities of polynomials with integer coefficients whose vari-
ables take values from finite subsets of the integers.
Definition 2 (Polynomial constraint over finite domains). An n−ary
constraint C whose n ∈ N+ variables take values from domains (Di )ni=1 is a
polynomial constraint over finite domains if and only if all domains are finite
subsets of Z and
n
Y n
Y
C = {x ∈ Di : p(x) ≥ 0} or C = {x ∈ Di : p(x) 6= 0} (20)
i=1 i=1
for a proper polynomial function p ∈ Π̃L of n integer variables, with integer
coefficients, and with multi-degree less than or equal to multi-index L ∈ Nn .
Observe that, with an abuse of notation that is normally accepted, the state-
ments p(x) ≥ 0 and p(x) 6= 0 can be used to refer to the corresponding con-
straints when the context makes the domains of variables evident.
Note that the two forms of polynomial constraints over finite domains identi-
fied in Definition 2 are not restrictive, and they can be used to refer to all equal-
ities, inequalities, and disequalities among polynomials. Actually, the choice of
such forms of constraints is justified by the following lemma, which is an adapta-
tion of the corresponding lemma introduced in other papers (e.g., [2]) to support
a canonical form for polynomial constraints over finite domains.
Lemma 1. Given two polynomial functions p ∈ Π̃L and q ∈ Π̃L of n ∈ N+
integer variables, with integer coefficients, and with multi-degree less than or
equal to multi-index L ∈ N n , the following co-implications hold
p(x) ≤ q(x) ⇐⇒ q(x) − p(x) ≥ 0, (21)
p(x) < q(x) ⇐⇒ q(x) − p(x) − 1 ≥ 0, (22)
p(x) > q(x) ⇐⇒ p(x) − q(x) − 1 ≥ 0, (23)
p(x) 6= q(x) ⇐⇒ p(x) − q(x) 6= 0, (24)
p(x) = q(x) ⇐⇒ p(x) − q(x) ≥ 0 ∧ q(x) − p(x) ≥ 0. (25)
Proof. The proof is trivially based on simple algebraic manipulations. t
u
Note that (22) and (23) are valid because p and q are polynomial functions of
integer variables with integer coefficients, and they are not valid for ordinary
polynomial functions of real variables. Also note that the application of (25)
increases the number of constraints because it turns one equality constraint into
two inequality constraints.
4 A Bounding Function Based on Interval Arithmetic
This section introduces sign consistency as a means to support reasoning on
polynomial constraints over finite domains. In the first part of this section, sign
consistency is defined as a form of local consistency parameterized in terms of a
bounding function. In the second part of this section, a bounding function based
on known results from the literature on interval arithmetic is proposed and
briefly studied. The application of the proposed bounding function to reason
on constraint satisfaction problems is discussed in Section 5, where preliminary
experimental results are also presented and discussed.
4.1 Sign consistency
The following definition of bounding function is intended to support the succes-
sive definition of sign consistency.
Definition 3 (Bounding function). A bounding function β is a computable
function that, given a nonempty integer box B ⊂ Zn and a polynomial function
p ∈ Π̃L of n ∈ N+ integer variables, with integer coefficients, and with multi-
degree less than or equal to multi-index L ∈ Nn , computes (p, p) ∈ R2 such that
the following conditions jointly hold
p ≤ min p(x) max p(x) ≤ p. (26)
x∈B x∈B
The proposed definition of bounding function is sufficient to state the follow-
ing parameterized definition of sign consistency.
Definition 4 (Sign consistency). Given a bounding function β and a polyno-
Qn n ∈ N+ variables take values from
mial constraint over finite domains C whose
nonempty domains (Di )ni=1 , with B = i=1 Di , a value v ∈ Di with 1 ≤ i ≤ n
is sign consistent for β with C if and only if
1. The constraint is p(x) ≥ 0, β(p, Bi→[v..v] ) = (p, p), and p ≥ 0; or
2. The constraint is p(x) 6= 0, β(p, Bi→[v..v] ) = (p, p), and p 6= 0 or p 6= 0.
A domain Di with 1 ≤ i ≤ n is sign consistent for β with C if and only if all its
values are sign consistent for β with C. Constraint C is sign consistent for β if
and only if all its domains are sign consistent for β with C.
The recalled definition of sign consistency is parameterized in terms of a
bounding function β, which is chosen to effectively reason on considered con-
straints. Three possible bounding functions are briefly mentioned in Section 1.
A very simple bounding function can be computed by exhaustively enumerating
the elements of the given box, which is always finite because the variables of
studied constraints take values from finite subsets of the integers. Such a bound-
ing function precisely computes the range of the studied polynomial function
over the given box, but it is obviously impractical even for moderately complex
problems. A less trivial bounding function can be computed using the Bernstein
form of polynomials (e.g., [7] for a survey of recent results and a historical retro-
spective). The use of such a bounding function is expected to be feasible only if
advanced algorithms (e.g., [8,10,13,14,20]) are adopted to compute the Bernstein
form of polynomials. Finally, a third bounding function can be defined on the
basis of a generalization for several variables [3] of known results for one [16] and
two [9] real variables whose values are restricted to the closed interval [0, 1]. The
computational cost of such a bounding function is expected to be lower than
that of the other two alternatives because it computes the value of considered
polynomial functions only at the corners of considered boxes. Unfortunately,
the lower and upper bounds that it provides are typically less stringent than
those provided by the other two alternatives, and therefore its effectiveness in
the satisfaction of constraints is reduced.
4.2 The proposed bounding function
Even if the bounding functions briefly mentioned above do not impose restric-
tions on treated constraints or on the domains of variables, their application to
solve practical constraint satisfaction problems is problematic for their inherent
computational cost. Preliminary experiments on their use to reason on moder-
ately complex constraints suggest that they are not effective in the solution of
practical problems. For this reason, the following bounding function is proposed
as a valid alternative to support the use of sign consistency to reason on practi-
cal constraint satisfaction problems. Note that the lower and upper bounds that
it provides are typically less stringent than those provided by the three bound-
ing functions mentioned above, but its simplicity and moderate computational
cost make it a viable alternative for practical applications, as witnessed by the
preliminary experimental results presented in Section 5.
Definition 5 (Bounding function βI ). Given a nonempty integer box B ⊂ Zn
and a polynomial function p ∈ Π̃L of n ∈ N+ integer variables, with integer
coefficients, and with multi-degree less than or equal to multi-degree L ∈ Nn , the
bounding function βI is
βI (p, B) = (p, p), (27)
where p(B) = [p..p].
The following proposition is relevant because it is sufficient to prove that βI
complies with the definition of bounding functions.
Proposition 1. Given a nonempty integer box B ⊂ Zn and a polynomial func-
tion p ∈ Π̃L of n ∈ N+ integer variables, with integer coefficients, and with
multi-degree less than or equal to multi-degree L ∈ Nn ,
p ≤ min p(x) max p(x) ≤ p, (28)
x∈B x∈B
where p(B) = [p..p].
Proof. The proof is trivially based on classic results from the literature on in-
terval arithmetic (e.g. [21]). t
u
Note that Proposition 1 is not surprising because the computation of p(B)
using interval arithmetic is precisely intended to compute an integer interval
that contains the range of the polynomial function p over the integer box B.
Unfortunately, the computed interval often largely overestimates the range of
the polynomial function p over the integer box B.
The following proposition is important because it quantifies the computa-
tional cost of the proposed bounding function. Note that the relevance of the
proposed bounding function to reason on polynomial constraints over finite do-
mains is motivated by its expected low computational cost.
Proposition 2. Given a nonempty integer box B ⊂ Zn and a polynomial func-
tion p ∈ Π̃L of n ∈ N+ integer variables, with integer coefficients, and with
multi-degree less than or equal to multi-degree L = (li )ni=1 ∈ Nn , the bounding
function βI can be computed using O(ln ) arithmetic operations in the worst case,
where l = max {li }ni=1 is the greatest degree of a variable in p.
Proof. The computation of βI essentially equals the evaluation of a polyno-
mial function, which can be performed using the multivariate Horner scheme
(e.g., [14]). The proposition is proved because the multivariate Horner scheme
requires O(ln ) arithmetic operations to evaluate the polynomial function p. t
u
Note that the lower and upper bounds computed by bounding function βI
can be improved using the following method to compute the m−th power of
a closed interval when m ∈ N+ is even. Actually, it is easy to verify that the
bounds computed using the following method are more stringent than the bounds
computed in terms of successive multiplications. The method is a classic result
from the literature on interval arithmetic and it is rephrased here for the sake
of completeness. In detail, given a closed interval A = [a, a] ⊂ R, and given an
even m ∈ N+
m m
[a , a ]
a≥0
m m
A = [a, a] = [am , am ] a<0 (29)
m m
[0, max{a , a }] otherwise.
Note that when m is odd Am can be computed in terms of successive multipli-
cations, which equals to state that Am = [a, a]m = [am , am ].
5 Preliminary Experiments
In order to use sign consistency as an effective means to support reasoning on
polynomial constraints over finite domains, a prototype implementation of a
specific algorithm has been recently included in the PolyFD library, which is
a C++ library for constraint satisfaction still at an early development stage.
The implemented algorithm enforces sign consistency on a constraint for a given
bounding function by removing sign-inconsistent values from the domains of
variables using a variant of the AC-3 algorithm [12]. The definition of sign con-
sistency ensures that removed values are not included in any assignment that
satisfies the constraint, and therefore the implemented algorithm can be used to
support constraint satisfaction. The computational cost needed to enforce sign
consistency using the implemented algorithm and the effectiveness of the algo-
rithm to support constraint satisfaction largely depend on the used bounding
function. Note that the current implementation of the PolyFD library is avail-
able upon request from authors, but it is not yet openly available to the research
community because it is still at an early development stage.
The remaining of this section is devoted to present (in alphabetical order)
five experiments on the use of the proposed bounding function to reason on well-
known constraint satisfaction problems. In order to assess the effectiveness of the
proposed approach, each problem was solved with the current prototype of the
PolyFD library and with Gecode [19], and the results were compared in terms of
execution time. In detail, each problem was solved 10 times using PolyFD and
the shortest execution time tP was recorded. Then, each problem was solved 10
times using Gecode and the shortest execution time tG was recorded. Finally, tP
and tG were compared. Note that both Gecode and PolyFD were configured to
use the same search heuristics and, for a fair comparison, some of the features
that Gecode implements were disabled because they are not yet implemented in
PolyFD. For example, even if some of the problems require that all variables are
assigned to different values, the specific filtering algorithm for the all-different
global constraint [15] that Gecode implements was not used. Finally, note that
Gecode has an established reputation for the advanced optimizations that it
implements, so the results of experiments are considered satisfactory to assess
the validity of the proposed bounding function to solve constraint satisfaction
problems if tP and tG are within the same order of magnitude.
The following experiments where performed using Gecode (version 5.1.0) and
PolyFD (version 2019.02.28) on a MacBook Air equipped with a 1.7 GHz Intel
Core i5 processor and with 4 GB of memory. The experimented Gecode programs
were based on available programs (http://www.hakank.org/gecode) with the
addition of minor changes. The introduced changes were intended to remove the
features of Gecode that are not yet implemented in PolyFD, and to ensure that
studied problems have only one solution.
Example 1 (Corner). This example uses eight integer variables whose domains
are initially set to interval [1..8]. Variables are enforced to be assigned to all
different values, and the following six additional constraints are imposed
x1 = 1 x4 = x1 + x6
x2 = 4 x5 = x3 + x8
x2 = x1 + x3 x7 = x6 + x8 .
The time tG needed by the Gecode implementation to find the single solution
to the problem, and the time tP needed by the PolyFD implementation to find
the same solution are
tG = 0.651 ms tP = 0.647 ms.
Note that PolyFD is roughly as fast as Gecode in finding the single solution to
the studied problem.
Example 2 (Dinner). This example uses three integer variables whose domains
are initially set to interval [1..100]. The following two constraints are imposed
on variables
6x1 + 4x2 + x3 = 40
x1 + x2 + x3 = 20.
The time tG needed by the Gecode implementation to find the single solution
to the problem, and the time tP needed by the PolyFD implementation to find
the same solution are
tG = 0.544 ms tP = 0.640 ms.
Note that PolyFD is 1.176 times slower than Gecode in finding the single solution
to the studied problem.
Example 3 (Donald). This example uses ten integer variables whose domains are
initially set to interval [0..9]. Variables are enforced to be assigned to all different
values, it is requested that x1 6= 0, x6 6= 0, and x8 6= 0, and the following three
additional constraints are imposed on variables
y1 = 100000x1 + 10000x2 + 1000x3 + 100x4 + 10x5 + x1
y2 = 100000x6 + 10000x7 + 1000x8 + 100x4 + 10x5 + x1
y1 + y2 = 100000x8 + 10000x2 + 1000x9 + 100x7 + 10x8 + x10 ,
where variables y1 and y2 are introduced for the sake of clarity but they are
not part of the problem. The time tG needed by the Gecode implementation to
find the single solution to the problem, and the time tP needed by the PolyFD
implementation to find the same solution are
tG = 1.152 ms tP = 1.112 ms.
Note that PolyFD is 1.035 times faster than Gecode in finding the single solution
to the studied problem.
Example 4 (Grocery). This example uses four integer variables whose domains
are initially set to interval [0..711]. It is requested that x1 ≤ x2 , x2 ≤ x3 , and
x3 ≤ x4 , and the following two additional constraints are imposed on variables
x1 · x2 · x3 · x4 = 711 · 106
x1 + x2 + x3 + x4 = 711.
The time tG needed by the Gecode implementation to find the single solution
to the problem, and the time tP needed by the PolyFD implementation to find
the same solution are
tG = 168.002 ms tP = 32.635 ms.
Note that PolyFD is 5.147 times faster than Gecode in finding the single solution
to the studied problem.
Example 5 (Safe). This example uses nine integer variables whose domains are
initially set to interval [1..9]. Variables are enforced to be all different, and the
following thirteen additional constraints are imposed on variables
x1 6= 1
x2 6= 2
..
.
x9 6= 9
x8 > x9
x7 = x4 − x6
x1 · x2 · x3 = x8 + x9
x2 + x3 + x6 < x8 .
The time tG needed by the Gecode implementation to find the single solution
to the problem, and the time tP needed by the PolyFD implementation to find
the same solution are
tG = 0.863 ms tP = 1.654 ms.
Note that PolyFD is 1.916 times slower than Gecode in finding the single solution
to the studied problem.
6 Conclusion
This paper introduced and studied a bounding function based on interval arith-
metic that is intended to make sign consistency a viable tool to solve practical
constraint satisfaction problems. The simplicity and the low computational cost
of the proposed bounding function make it a feasible option to treat practical
constraint satisfaction problems, even if the bounds that it provides are less
stringent than the bounds provided by other bounding functions.
In order to assess the applicability of the proposed bounding function to
practical problems, preliminary experiments were performed to compare the per-
formance of PolyFD, a prototype C++ library that uses the proposed bounding
function, with the performance of Gecode. Notably, even if the programs that
use PolyFD are sometimes slower than the corresponding programs that use
Gecode, measured execution times are always within the same order of magni-
tude. In particular, in the worst case, the program that uses PolyFD is roughly
twice as slow as the corresponding program that uses Gecode. On the contrary,
in the best case, the program that uses PolyFD is more than five times faster the
corresponding program that uses Gecode. Given that Gecode has an established
reputation for the advanced level of optimizations that it implements, despite
being preliminary, obtained experimental results can be considered encouraging.
A planned development of the presented work regards the addition of further
experiments to the list of studied problems to improve the understanding of the
feasibility of the proposed bounding function to reason on practical constraint
satisfaction problems. Then, some optimizations on the implementation of the
proposed bounding function have already been planned to take advantage of the
sparsity patterns of polynomials. Given that the effectiveness of the implemented
algorithm for sign-consistency enforcement largely depends on the computational
cost of the adopted bounding function, improvements in the implementation of
the proposed bounding function are expected to affect performance significantly.
Finally, the improvement of the overall quality of the current implementation of
PolyFD has already been planned in order to make it openly available to the
research community of potentially interested users.
References
1. Apt, K.: Principles of Constraint Programming. Cambridge University Press (2003)
2. Bergenti, F., Monica, S.: Hyper-arc consistency of polynomial constraints over finite
domains using the modified Bernstein form. Annals of Mathematics and Artificial
Intelligence 80(2), 131–151 (2017)
3. Bergenti, F., Monica, S.: Satisfaction of polynomial constraints over finite domains
using function values. In: Della Monica, D., Murano, A., Rubin, S., Sauro, L. (eds.)
ICTCS 2017 and CILC 2017 Italian Conference on Theoretical Computer Science
and Italian Conference on Computational Logic. CEUR Workshop Proceedings,
vol. 1949, pp. 262–275. RWTH Aachen (2017)
4. Bergenti, F., Monica, S., Rossi, G.: Polynomial constraint solving over finite do-
mains with the modified Bernstein form. In: Fiorentini, C., Momigliano, A. (eds.)
CILC 2016 Italian Conference on Computational Logic. CEUR Workshop Proceed-
ings, vol. 1645, pp. 118–131. RWTH Aachen (2016)
5. Bergenti, F., Monica, S., Rossi, G.: A subdivision approach to the solution of
polynomial constraints over finite domains using the modified Bernstein form. In:
Adorni, G., Cagnoni, S., Gori, M., Maratea, M. (eds.) AI*IA 2016 Advances in
Artificial Intelligence. Lecture Notes in Computer Science, vol. 10037, pp. 179–
191. Springer (2016)
6. Bergenti, F., Monica, S., Rossi, G.: Constraint logic programming with polynomial
constraints over finite domains. Fundamenta Informaticae 161(1–2), 9–27 (2018)
7. Farouki, R.T.: The Bernstein polynomial basis: A centennial retrospective. Com-
puter Aided Geometric Design 29(6), 379–419 (2012)
8. Farouki, R.T., Rajan, V.T.: Algorithms for polynomials in Bernstein form.
Computer-Aided Geometric Design 5(1), 1–26 (1988)
9. Garloff, J.: Convergent bounds for the range of multivariate polynomials. In: Nickel,
K. (ed.) Interval Mathematics 1985. Lecture Notes in Computer Science, vol. 212,
pp. 37–56. Springer (1986)
10. Garloff, J., Smith, A.P.: Solution of systems of polynomial equations by using
Bernstein expansion. In: Alefeld, G., Rohn, J., Rump, S., Yamamoto, T. (eds.)
Symbolic Algebraic Methods and Verification Methods. pp. 87–97. Springer (2001)
11. von zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University
Press (2003)
12. Mackworth, A.: Consistency in networks of relations. Artificial Intelligence 8, 99–
118 (1977)
13. Ray, S., Nataraj, P.: An efficient algorithm for range computation of polynomials
using the Bernstein form. Journal of Global Optimization 45, 403–426 (2009)
14. Ray, S., Nataraj, P.: A matrix method for efficient computation of Bernstein coef-
ficients. Reliable Computing 17, 40–71 (2012)
15. Régin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Pro-
ceedings of the National Conference on Artificial Intelligence (AAAI 1994). pp.
362–367. AAAI (1994)
16. Rivlin, T.J.: Bounds on a polynomial. Journal of Research of the National Bureau
of Standards 74B(1), 47–54 (1970)
17. Rossi, F., van Beek, P., Walsh, T.: Handbook of Constraint Programming. Elsevier,
New York (2006)
18. Ruszczyński, A.: Nonlinear Optimization. Princeton University Press (2006)
19. Schulte, C., Stuckey, P.J.: Efficient constraint propagation engines. ACM Transac-
tions on Programming Languages and Systems 31(1), 1–43 (2008)
20. Smith, A.P.: Fast construction of constant bound functions for sparse polynomials.
Journal of Global Optimization 43(2), 445–458 (2009)
21. Tucker, W.: Validated numerics: A short introduction to rigorous computations.
Princeton University Press (2011)