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

Bergenti F.;Monica S.
2019

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.
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 Dimensione Formato  
AMAI2019a - Published.pdf

Accesso riservato

Dimensione 491.9 kB
Formato Adobe PDF
491.9 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1207018
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact