Z3 在运行多次时产生不同的模型

Question

我已经将 Z3 与 JAVA 绑定一起使用 2 年了。出于某种原因，我总是自己生成 SMTLib2 代码作为字符串，然后使用 parseSMTLib2String 构建相应的 Z3 Expr。据我所知，每次我用这种方法输入完全相同的输入两次，我总是得到相同的模型。

但我最近决定更改并直接使用 JAVA API 并使用 ctx.mk...() 构建表达式。基本上，我不是生成字符串然后解析它，而是让 Z3 完成构建 Z3 Expr 的工作。

现在发生的事情是我得到了不同的模型，同时我检查了求解器是否确实存储了完全相同的代码。我的 JAVA 代码看起来像这样：

static final Context context = new Context();
static final Solver solver = context.mkSolver();

public static void someFunction(){
    solver.add(context.mk...()); // Add some bool expr to the solver
    Status status = solver.check();
    if(status == SATISFIABLE){
        System.out.println(solver.getModel()); // Prints different model with same expr
    }
}

我在运行时间内对 "someFunction()" 进行了 1 次以上调用，并且检查的表达式 context.mk...() 发生了变化。但是如果我运行我的程序两次，相同的表达式序列会被检查，有时会给我一个运行另一个不同的模型。

我试过禁用自动配置参数并设置我自己的随机种子，但 Z3 有时仍会生成不同的模型。我只使用有界整数变量和未解释的函数。我是否以错误的方式使用了 API？

如果需要，我可以将整个 SMTLib2 代码添加到这个问题中，但它并不是很短并且包含多个求解器调用（我什至不知道它们中的哪一个会从一个执行到另一个产生不同的模型，我只知道有人这样做）。

我必须准确地说我已经阅读了以下主题，但发现答案已经过时或（如果我理解正确的话）支持 "Z3 is deterministic and should produce the same model for the same input":

Z3 timing variation

Randomness in Z3 Results

different run time for the same code in Z3

编辑： 令人惊讶的是，使用以下代码，我似乎总是得到相同的模型，而 Z3 现在似乎是确定性的。但是，与我以前的代码相比，内存消耗很大，因为我需要将上下文保留在内存中一段时间。知道我可以做些什么来以更少的内存使用实现相同的行为吗？

public static void someFunction(){
    Context context = new Context();
    Solver solver = context.mkSolver();
    solver.add(context.mk...()); // Add some bool expr to the solver
    Status status = solver.check();
    if(status == SATISFIABLE){
        System.out.println(solver.getModel()); // Seem to always print the same model :-)
    }
}

这是我多次调用"someFunction"方法的内存消耗：

Answer 1

只要不是在同一个问题上在 SAT 和 UNSAT 之间切换，就不是错误。

您链接的其中一个答案解释了正在发生的事情：

Randomness in Z3 Results

"That being said, if we solve the same problem twice in the same execution path, then Z3 can produce different models. Z3 assigns internal unique IDs to expressions. The internal IDs are used to break ties in some heuristics used by Z3. Note that the loop in your program is creating/deleting expressions. So, in each iteration, the expressions representing your constraints may have different internal IDs, and consequently the solver may produce different solutions."

也许在解析时分配相同的 ID，而 API 可能会有所不同，尽管我觉得这有点难以置信...

如果您需要这种行为并且您确定它是通过 SMT 编码实现的，您可以随时打印 API 中的表达式然后解析它们。

Answer 2

我想我发现了产生这些奇怪的相反行为的代码的特定部分。如果我完全错了，也许周围的 Z3 专家可以告诉我。

首先，如果我在我的程序的单个运行中尝试两次相同的代码（无论是手动生成的代码还是使用 API 生成的代码），我有时会结束与不同的模型。这是我以前没有注意到的，这对我来说实际上不是真正的问题。

然而，我主要担心的是如果我运行我的程序两次，在两次运行期间检查完全相同的代码会发生什么。

当我手动生成代码时，我最终得到这样的函数定义：

(declare-fun var!0 () Int)
(declare-fun var!2 () Int)
(declare-fun var!42 () Int)

(assert (and
    (or (= var!0 0) (= var!0 1))
    (or (= var!2 0) (= var!2 1))
    (or (= var!42 0) (= var!42 1))
))

(define-fun fun ((i! Int)) Int
    (ite (= i! 0) var!0
        (ite (= i! 1) var!2
            (ite (= i! 2) var!42 -1)
        )
    )            
)

据我所知（以及我所读到的相关内容（参见 here）），API 无法按照我定义的方式处理 "fun" 功能。所以我用 API 定义它是这样的：

(declare-fun var!0 () Int)
(declare-fun var!2 () Int)
(declare-fun var!42 () Int)

(assert (and
    (or (= var!0 0) (= var!0 1))
    (or (= var!2 0) (= var!2 1))
    (or (= var!42 0) (= var!42 1))
))

(declare-fun fun (Int) Int)
(assert (forall
    ((i! Int))
    (ite (= i! 0) (= (fun i!) var!0)
        (ite (= i! 1) (= (fun i!) var!2)
            (ite (= i! 2) (= (fun i!) var!42) (= (fun i!) -1))
        )
    )
))

似乎使用第一种方法，总是（或者至少如此频繁，以至于对我来说这不是真正的问题）检查不同运行的相同代码给出了相同个型号。

使用第二种方法，检查不同运行的相同代码通常会得到 不同的 模型。

谁能告诉我我所揭示的关于 Z3 实际工作原理的背后是否确实存在一些逻辑？

因为我需要我的结果尽可能的可重现，所以我回到了手动代码生成，它似乎工作得很好。我很想看到 API 中的函数允许我们直接定义函数，而不必使用 "forall" 方法，看看我刚才描述的是否正确。

Z3 在运行多次时产生不同的模型

Z3 producing different models when run multiple times

java

model

z3

non-deterministic

Z3 在 运行 多次时产生不同的模型

Z3 producing different models when run multiple times

java

model

z3

non-deterministic

Z3 在运行多次时产生不同的模型