Fixes for bounds on transcendental functions (#3832)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Mon, 9 Mar 2020 14:33:14 +0000 (09:33 -0500)
committerGitHub <noreply@github.com>
Mon, 9 Mar 2020 14:33:14 +0000 (09:33 -0500)
commit31e30d52a3fc6ac2a2a2f5e8d4a17a4ca954d8e8
tree5fff7664d1571d1122a746a0b0fcc01a369b84a4
parente3110121a3f19ba1594a9b54f7f332804fd2e2af
Fixes for bounds on transcendental functions (#3832)

This PR refactors and fixes how bounds are set for transcendental functions. The new code ensures that all transcendental function applications are given bounds. (Our previous failures to do so were hindering our ability to say "sat", due to NlModel::checkModel failures).

There were previously two issues on why transcendental function applications were not being assigned bounds:

"Slave" transcendental functions (e.g. those that we reduce via sin(t) = sin(y) ^ -pi <= y <= pi ^ y + 2*pi*N = t) were not being given bounds explicitly,
Transcendental functions that are congruent to others (e.g. f(x) where f(y) exists and x=y in the current context) were being ignored and hence not bound.
This PR clarifies the master/slave relationship that tracks which transcendental function applications have been purified, and furthermore tracks congruence classes.

The setting of bounds and the check-model is further simplified by setting bounds on the original terms, whereas the current code sets bounds on the model values of terms. In other words, previously if we had term sin(y) and y^M = c, then we'd set bounds for sin(c), whereas the new code sets the bound on sin(y) directly.

Fixes #3783. We answer unknown without an assertion failure on that benchmark now. Further work based on ignoring literals from internally generated lemmas is necessary for solving it sat.
src/theory/arith/arith_utilities.cpp
src/theory/arith/nl_model.cpp
src/theory/arith/nl_model.h
src/theory/arith/nonlinear_extension.cpp
src/theory/arith/nonlinear_extension.h