Polynomial constraints over nite domains are expressed as equalities, inequalities, and disequalities of polynomials with integer coe cients whose variables take values from nite 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 speci cally to support reasoning on polynomial constraints over nite domains. Sign consistency is parameterized 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 nite 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 e ectively reason on polynomial constraints over nite domains.
Polynomials are ubiquitous because they are the basis of important applications
in virtually all elds of science and engineering. In addition, the in uential
literature on computer algebra witnesses the advanced level of understanding of
polynomials from a computational point of view (e.g., [
Sign consistency is de ned and studied in an upcoming paper as a type
of local consistency (e.g., [
Polynomial constraints over nite domains are expressed as equalities, inequalities, and disequalities of polynomials whose variables take values from nite subsets of the integers. Therefore, the satis ability 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 nite domains. In particular, sign consistency delegates the study of the sign of polynomial functions to a bounding function that is chosen to adapt it to the characteristics of the studied problem. The chosen bounding function is expected to provide e ective 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
dened. A very simple bounding function can be de ned in terms of the exhaustive
enumeration of the elements of the given box, which is always nite because the
variables of studied constraints take values from nite subsets of the integers.
Such a bounding function is obviously impractical even for moderately complex
problems. A less trivial bounding function can be de ned using classic results
on the Bernstein form of polynomials (e.g., [
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 nite 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., [
This paper is organized as follows. Section 2 provides a self-contained presentation of adopted notation, which includes the notation borrowed from interval arithmetic. Section 3 presents polynomial constraints over nite domains in the scope of constraint satisfaction problems. Section 4 introduces sign consistency and discusses the proposed bounding function. Section 5 shows preliminary experimental 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
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 polynomial 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 speci c notation is also introduced to study polynomial functions with integer coe cients whose variables take values from nite 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 2 N+, a multi-index I 2 Nn is de ned as an n tuple of natural numbers n
I = (i1; i2; : : : ; in) = (ik)k=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 2 Nn as an exponent for t 2 Rn with t = (t1; t2; : : : ; tn) = (tk)kn=1 tI = n Y tikk ; 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 2 Nn and J 2 Nn, they can be compared using the following partial order
I
J () i1 j1 ^ i2 j2 ^ ^ in jn and they can be added componentwise
I + J = (i1 + j1; i2 + j2; : : : ; in + jn): The following abbreviation is introduced for multi-indices H 2 Nn, I 2 Nn, and J 2 Nn to express repeated sums
j1 X ( ) = X j2 X jn
X ( ): 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)kn=1.
Using the multi-index notation, a polynomial function p : Rn 7! R of n 2 N+ real variables with real coe cients can be expressed as where faI gI L R is the set of the coe cients of p, and multi-index L 2 Nn is the multi-degree of p. The vector space of polynomial functions of n 2 N+ real variables, with real coe cients, and with multi-degree less than or equal to multi-index L 2 Nn is
L = spanRfPI gI L
PI : Rn 7! R
PI (x) = xI : Similarly, a polynomial function p~ : Zn 7! Z of n 2 N+ integer variables with integer coe cients can be expressed as p(x) =
X aI xI ;
I L p~(x) =
X a~I xI ;
I L where fa~I gI L Z is the set of the coe cients of p~, and multi-index L 2 Nn is the multi-degree of p~. The vector space of polynomial functions of n 2 N+ integer variables, with integer coe cients, and with multi-degree less than or equal to multi-index L 2 Nn is ~ L = spanZfP~I gI L
P~I : Zn 7! Z
P~I (x) = xI : (3) (4) (5) (6) (7) (8) (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 2 R to a 2 R is denoted as [a; a] = fx 2 R : a x ag; and it equals the empty set if and only if a > a. A singleton (real) interval that contains only a 2 R is denoted as [a] = [a; a]. Given n 2 N+, a (real) box B Rn from b = (bk)kn=1 2 Rn to b = (bk)kn=1 2 Rn is denoted as
B = [b; b] = [b1; b1] and they can be multiplied
A + C = [a + c; a + c];
A C = [minfa c; a c; a c; a cg; maxfa c; a c; a c; a cg]: 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 2 Z to c 2 Z is denoted as [c::c] = fx 2 Z : c x cg; and it equals the empty set if and only if c > c. A singleton integer interval that contains only c 2 Z is denoted as [c] = [c::c]. Given n 2 N+, an integer box D Zn from d = (dk)kn=1 2 Zn to d = (dk)kn=1 2 Zn is denoted as D = [d::d] = [d1::d1] [d2::d2] [dn::dn]; 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 nite integer set A Zn is the inclusion-minimal integer box such that A A.
Interval arithmetic (e.g., [
X[aI ]BI ;
I L
Using the introduced notation, which is borrowed from interval arithmetic, a
polynomial function p : Rn 7! R of n 2 N+ real variables with real coe cients
can be extended to work on boxes. If polynomial p is expressed as in (6), then
for any box B Rn
where the notation for singleton intervals is used to treat the coe cients 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., [
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 de ned previously can be used to express the evaluation of a polynomial function p~ of n 2 N+ integer variables with integer coe cients when an integer box D Zn is used as argument. 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 nite domains in the scope of
constraint satisfaction problems. Note that polynomial constraints over nite
domains have been already studied in the scope of constraint logic programming in
previous papers [
The following ordinary nomenclature on constraint satisfaction problems
(e.g., [
De nition 1 (Constraint, assignment, and satis ability). An n ary constraint C whose n 2 N+ variables take values from domains (Di)in=1 is a subset of the Cartesian product of the domains of variables
C n Y Di: i=1 An assignment a of the variables of C is an element of the Cartesian product of the domains of variables An assignment of the variables of C satis es C if and only if a 2 C. A constraint C is satis able if there exists at least one assignment of its variables that satis es the constraint (i.e., C 6= ;). On the contrary, a constraint C is unsatis able if no such an assignment exists (i.e., C = ;).
The following de nition captures the informal statement that describes polynomial constraints over nite domains as constraints expressed as equalities, inequalities, and disequalities of polynomials with integer coe cients whose variables take values from nite subsets of the integers.
De nition 2 (Polynomial constraint over nite domains). An n ary constraint C whose n 2 N+ variables take values from domains (Di)in=1 is a polynomial constraint over nite domains if and only if all domains are nite subsets of Z and
C = fx 2 n Y Di : p(x) i=1 0g or
C = fx 2 n Y Di : p(x) 6= 0g i=1 (20) for a proper polynomial function p 2 ~ L of n integer variables, with integer coe cients, and with multi-degree less than or equal to multi-index L 2 Nn.
Observe that, with an abuse of notation that is normally accepted, the statements p(x) 0 and p(x) 6= 0 can be used to refer to the corresponding constraints when the context makes the domains of variables evident.
Note that the two forms of polynomial constraints over nite domains
identied in De nition 2 are not restrictive, and they can be used to refer to all
equalities, inequalities, and disequalities among polynomials. Actually, the choice of
such forms of constraints is justi ed by the following lemma, which is an
adaptation of the corresponding lemma introduced in other papers (e.g., [
q(x) () q(x) p(x) < q(x) () q(x) p(x) > q(x) () p(x) p(x) 6= q(x) () p(x) p(x) = q(x) () p(x) p(x) p(x) q(x) q(x) 6= 0; q(x) 0; 1 1 0; 0; 0 ^ q(x) p(x) 0: Proof. The proof is trivially based on simple algebraic manipulations. Note that (22) and (23) are valid because p and q are polynomial functions of integer variables with integer coe cients, 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 nite domains. In the rst part of this section, sign consistency is de ned 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 brie y 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
The following de nition of bounding function is intended to support the successive de nition of sign consistency.
De nition 3 (Bounding function). A bounding function is a computable function that, given a nonempty integer box B Zn and a polynomial function p 2 ~ L of n 2 N+ integer variables, with integer coe cients, and with multidegree less than or equal to multi-index L 2 Nn, computes (p; p) 2 R2 such that the following conditions jointly hold (21) (22) (23) (24) (25) tu p
The proposed de nition of bounding function is su cient to state the following parameterized de nition of sign consistency.
De nition 4 (Sign consistency). Given a bounding function and a polynomial constraint over nite domains C whose n 2 N+ variables take values from nonempty domains (Di)in=1, with B = Qin=1 Di, a value v 2 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 de nition of sign consistency is parameterized in terms of a
bounding function , which is chosen to e ectively reason on considered
constraints. Three possible bounding functions are brie y mentioned in Section 1.
A very simple bounding function can be computed by exhaustively enumerating
the elements of the given box, which is always nite because the variables of
studied constraints take values from nite subsets of the integers. Such a
bounding 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., [
Even if the bounding functions brie y mentioned above do not impose restrictions 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 moderately complex constraints suggest that they are not e ective 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 practical constraint satisfaction problems. Note that the lower and upper bounds that it provides are typically less stringent than those provided by the three bounding 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.
De nition 5 (Bounding function I ). Given a nonempty integer box B Zn and a polynomial function p 2 ~ L of n 2 N+ integer variables, with integer coe cients, and with multi-degree less than or equal to multi-degree L 2 Nn, the bounding function I is where p(B) = [p::p].
I (p; B) = (p; p);
The following proposition is relevant because it is su cient to prove that I complies with the de nition of bounding functions.
Proposition 1. Given a nonempty integer box B Zn and a polynomial function p 2 ~ L of n 2 N+ integer variables, with integer coe cients, and with multi-degree less than or equal to multi-degree L 2 Nn, where p(B) = [p::p].
p
Proof. The proof is trivially based on classic results from the literature on
interval arithmetic (e.g. [
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 quanti es the computational cost of the proposed bounding function. Note that the relevance of the proposed bounding function to reason on polynomial constraints over nite domains is motivated by its expected low computational cost.
Proposition 2. Given a nonempty integer box B Zn and a polynomial function p 2 ~ L of n 2 N+ integer variables, with integer coe cients, and with multi-degree less than or equal to multi-degree L = (li)in=1 2 Nn, the bounding function I can be computed using O(ln) arithmetic operations in the worst case, where l = max fligin=1 is the greatest degree of a variable in p.
Proof. The computation of I essentially equals the evaluation of a
polynomial function, which can be performed using the multivariate Horner scheme
(e.g., [
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 2 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 (27) (28) tu 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 2 N+
8>[am; am] Am = [a; a]m = <[am; am] a 0 a < 0 >:[0; maxfam; amg] otherwise: (29) Note that when m is odd Am can be computed in terms of successive multiplications, which equals to state that Am = [a; a]m = [am; am]. 5
In order to use sign consistency as an e ective means to support reasoning on
polynomial constraints over nite domains, a prototype implementation of a
speci c 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 [
The remaining of this section is devoted to present (in alphabetical order)
ve experiments on the use of the proposed bounding function to reason on
wellknown constraint satisfaction problems. In order to assess the e ectiveness of the
proposed approach, each problem was solved with the current prototype of the
PolyFD library and with Gecode [
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 di erent values, and the following six additional constraints are imposed x1 = 1 x2 = 4 x2 = x1 + x3 x4 = x1 + x6 x5 = x3 + x8 x7 = x6 + x8: The time tG needed by the Gecode implementation to nd the single solution to the problem, and the time tP needed by the PolyFD implementation to nd the same solution are tG = 0:651 ms tP = 0:647 ms: Note that PolyFD is roughly as fast as Gecode in nding 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 nd the single solution to the problem, and the time tP needed by the PolyFD implementation to nd the same solution are tG = 0:544 ms tP = 0:640 ms: Note that PolyFD is 1:176 times slower than Gecode in nding 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 di erent 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 nd the single solution to the problem, and the time tP needed by the PolyFD implementation to nd the same solution are
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 nd the single solution to the problem, and the time tP needed by the PolyFD implementation to nd the same solution are Note that PolyFD is 5:147 times faster than Gecode in nding 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 di erent, and the following thirteen additional constraints are imposed on variables x1 6= 1 The time tG needed by the Gecode implementation to nd the single solution to the problem, and the time tP needed by the PolyFD implementation to nd the same solution are tG = 0:863 ms tP = 1:654 ms: Note that PolyFD is 1:916 times slower than Gecode in nding the single solution to the studied problem.
This paper introduced and studied a bounding function based on interval arithmetic 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 performance 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 magnitude. 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 ve 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 e ectiveness 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 a ect performance signi cantly. 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.