SMT 中的混合理论

Question

我想构建一个 SMT 公式，其中包含一些关于整数线性算术和布尔变量的断言，以及一些关于真实非线性算术和布尔变量的断言。对整数和实数的断言仅共享布尔变量。例如，考虑以下公式：

(declare-fun b () Bool)
(assert (= b true))

(declare-fun x () Int)
(declare-fun y () Int)
(declare-fun z () Int)
(assert (or (not b) (>= (+ x y) (- x (+ (* 2 z) 1)))))

(declare-fun r () Real)
(assert (or (not b) (= (+ (* r r) (* 3 r) (- 4)) 0)))

如果我用这个公式喂 z3，它会立即报告 "unknown"。但是如果我删除它的整数部分，我马上得到解决方案，它满足变量 "r" 的约束。我认为这意味着非线性约束本身对求解器来说并不困难。问题应该在于混合对整数的（线性）约束和对实数的（非线性）约束。

所以我的问题如下。使用 z3（如果有的话）处理这种混合公式的正确方法是什么？我对 DPLL(T) 的理解是它应该能够针对不同的约束使用不同的理论求解器来处理此类公式。如有错误请指正

Answer 1

正如 George 在他的评论中所说，Z3 中的非线性求解器相当脆弱，开箱即用的性能也不是很好。也就是说，在 Whosebug 上有很多关于此问题的问题和答案，例如，请参阅这些：

Z3 Performance with Non-Linear Arithmetic

How does Z3 handle non-linear integer arithmetic?

Non-linear arithmetic and uninterpreted functions

Z3 Theorem Prover: Pythagorean Theorem (Non-Linear Artithmetic)

Which techniques are used to handle Non-linear Integer Real problems in z3?

Satisfiablity checking in non-linear integer arithmetic by approximation

SMT 中的混合理论

Mixing theories in SMT

z3

smt

dpll