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. - STAMPA. - 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;ROSSI, Gianfranco
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.
9783319491295
9783319491295
A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form / Bergenti, Federico; Monica, Stefania; Rossi, Gianfranco. - STAMPA. - 10037:(2016), pp. 179-191. [10.1007/978-3-319-49130-1_14]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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