This paper proposes an algorithm to reason on constraints expressed in terms of polynomials with integer coefficients whose variables take values from finite subsets of the integers. The proposed algorithm assumes that an initial approximation of the domains of variables is available in terms of a bounding box, and it recursively subdivides the box into disjoint boxes until a termination condition is met. The algorithm includes three termination conditions that allow using it for three related reasoning tasks: constraint satisfaction, enumeration of solutions, and hyper-arc consistency enforcement. Considered termination conditions are based on suitable lower and upper bounds for polynomial functions over boxes that are determined using new results proved in the paper. The algorithm is particularly appropriate to reason on high-degree polynomial constraints because the proposed method to determine lower and upper bounds can outperform alternative methods when high-degree polynomials in a moderate number of variables are considered.

A subdivision algorithm to reason on high-degree polynomial constraints over finite domains / Bergenti, F.; Monica, S.. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 87:4(2019), pp. 343-360. [10.1007/s10472-019-09680-4]

### A subdivision algorithm to reason on high-degree polynomial constraints over finite domains

#### Abstract

This paper proposes an algorithm to reason on constraints expressed in terms of polynomials with integer coefficients whose variables take values from finite subsets of the integers. The proposed algorithm assumes that an initial approximation of the domains of variables is available in terms of a bounding box, and it recursively subdivides the box into disjoint boxes until a termination condition is met. The algorithm includes three termination conditions that allow using it for three related reasoning tasks: constraint satisfaction, enumeration of solutions, and hyper-arc consistency enforcement. Considered termination conditions are based on suitable lower and upper bounds for polynomial functions over boxes that are determined using new results proved in the paper. The algorithm is particularly appropriate to reason on high-degree polynomial constraints because the proposed method to determine lower and upper bounds can outperform alternative methods when high-degree polynomials in a moderate number of variables are considered.
##### Scheda breve Scheda completa Scheda completa (DC) 2019
87
4
343
360
A subdivision algorithm to reason on high-degree polynomial constraints over finite domains / Bergenti, F.; Monica, S.. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 87:4(2019), pp. 343-360. [10.1007/s10472-019-09680-4]
Bergenti, F.; Monica, S.
File in questo prodotto:
File
AMAI2019a - Published.pdf

Accesso riservato

Dimensione 491.9 kB Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1207018`
• ND
• 0
• 0