This paper discusses an algorithm to solve polynomial constraints over finite domains, namely constraints which are expressed in terms of equalities, inequalities and disequalities of polynomials with integer coefficients whose variables are associated with finite domains. The proposed algorithm starts with a preliminary step intended to rewrite all constraints to a canonical form. Then, the modified Bernstein form of obtained polynomials is used to recursively restrict the domains of variables, which are assumed to be initially approximated by a bounding box. The proposed algorithm proceeds by subdivisions, and it ensures that each variable is eventually associated with the inclusion maximal finite domain in which the set of constraints is satisfiable. If arbitrary precision integer arithmetic is available, no approximation is introduced in the solving process because the coefficients of the modified Bernstein form are integer numbers.

A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form / Bergenti, Federico; Monica, Stefania; Rossi, Gianfranco. - 10037:(2016), pp. 179-191. [10.1007/978-3-319-49130-1_14]

A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form

BERGENTI, Federico;MONICA, Stefania;
2016

Abstract

This paper discusses an algorithm to solve polynomial constraints over finite domains, namely constraints which are expressed in terms of equalities, inequalities and disequalities of polynomials with integer coefficients whose variables are associated with finite domains. The proposed algorithm starts with a preliminary step intended to rewrite all constraints to a canonical form. Then, the modified Bernstein form of obtained polynomials is used to recursively restrict the domains of variables, which are assumed to be initially approximated by a bounding box. The proposed algorithm proceeds by subdivisions, and it ensures that each variable is eventually associated with the inclusion maximal finite domain in which the set of constraints is satisfiable. If arbitrary precision integer arithmetic is available, no approximation is introduced in the solving process because the coefficients of the modified Bernstein form are integer numbers.
AI*IA 2016 Advances in Artificial Intelligence
Giovanni Adorni Stefano Cagnoni Marco Gori Marco Maratea
9783319491295
Springer International Publishing
A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form / Bergenti, Federico; Monica, Stefania; Rossi, Gianfranco. - 10037:(2016), pp. 179-191. [10.1007/978-3-319-49130-1_14]
Bergenti, Federico; Monica, Stefania; Rossi, Gianfranco
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento 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/1207014
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact