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, Federico; Monica, Stefania. - In: ANNALS OF MATHEMATICS AND OF ARTIFICIAL INTELLIGENCE. - ISSN 1012-2443. - 87:(2019), pp. 343-360. [10.1007/s10472-019-09680-4]
A subdivision algorithm to reason on high-degree polynomial constraints over finite domains
BERGENTI Federico
;MONICA Stefania
2019-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.