Improvements and fixes in cegqi arithmetic (#2247)
authorAndrew Reynolds <andrew.j.reynolds@gmail.com>
Thu, 2 Aug 2018 02:24:42 +0000 (21:24 -0500)
committerAndres Noetzli <andres.noetzli@gmail.com>
Thu, 2 Aug 2018 02:24:42 +0000 (19:24 -0700)
commitea426344ed44b28dcdbe4e631b52250ecef0551f
tree2d418d4691f49412761990e591092f304b92e380
parent551f82a1398c97a5cd1f75b2c411b6fe464cc6ec
Improvements and fixes in cegqi arithmetic (#2247)

This includes several improvements for cegqi with arithmetic:
- Randomly choose either lower or upper bounds instead of always using lower bounds (this is similar to cegqi+BV),
- Equalities are handled by processAssertions,
- Resort to *only* model values at full effort instead of trying to mix model values/bounds (this is also similar to cegqi+BV),
- cegqi+arithmetic does not try multiple instantiations unless the flag cbqiMultiInst is set. This makes it so that ceg_instantiator does not have exponential behavior when the strategy is non-monotonic.

It also includes a core fix to computing what bound is optimal based on an ordering that incorporates virtual terms. Previously, we would consider, e.g.:
`a+b*delta > c+d*delta if a>=c and b>=d`
Whereas the correct check is lexicographic:
`a+b*delta > c+d*delta if a>c or a=c and b>d`
This means e.g. 2+(-1)*delta > 3 was previously wrongly inferred.

This is part of merging https://github.com/ajreynol/CVC4/tree/cegqiSingleInst, which is +3-0 on SMTLIB BV and +12-9 on SMTLIB LIA+LRA+NRA+NIA.
src/theory/quantifiers/cegqi/ceg_arith_instantiator.cpp
test/regress/Makefile.tests
test/regress/regress1/quantifiers/RND_4_1-existing-inst.smt2 [new file with mode: 0644]
test/regress/regress1/quantifiers/repair-const-nterm.smt2 [new file with mode: 0644]