Implement aggressive pruning in CAD solver (#7650)
authorGereon Kremer <gkremer@stanford.edu>
Wed, 17 Nov 2021 06:41:51 +0000 (22:41 -0800)
committerGitHub <noreply@github.com>
Wed, 17 Nov 2021 06:41:51 +0000 (06:41 +0000)
commit09e934c84777ef4dbc74b19e22ec24a1c643c71b
treeb085c6d188bcc7e6b39a33b13ec53588ecb7e1d7
parentd4183fd0318585e089e805e97f8123cd8f84ace5
Implement aggressive pruning in CAD solver (#7650)

This PR implements a more aggressive pruning of redundant intervals, namely intervals that are covered by two other intervals, but not a single one. As already discussed in the respective paper, it is not entirely clear whether this is beneficial as removing such an interval may make the "overlap" smaller and thus the generated interval in the lower dimension may become smaller as well. It is thus only enabled via a (new) option.
Experiments show that such redundant intervals are relatively common (878 benchmarks on QF_NRA), the impact of this option is very limited and not strictly beneficial.
src/options/arith_options.toml
src/theory/arith/nl/cad/cdcac.cpp
src/theory/arith/nl/cad/cdcac_utils.cpp
src/theory/arith/nl/cad/cdcac_utils.h