Z3 获取最后一个有效模型

Z3 getting last valid model

我使用 Z3 C++ api 找到一个可满足的公式，该公式对于某些布尔变量（让我们称它们为 b0，...，bn）为真而言是最小的。

我有一个包含布尔变量 b0,...,bn 的公式，我想找到一些可满足的公式，其中我将最少数量的 b0,...,bn 设置为 true。

我首先找到 b0,...,bn 的一个子集，可以分配给 true 并满足我的公式，然后我逐渐要求求解器找到更小的子集（即这些布尔变量之一被翻转为 false）。

当我找不到更小的子集时，我找到了我的局部最小值，即我从 Z3 得到了不满意的结果。此时，我想访问最后一个有效模型。

这可能吗？当对 "check" 的调用不满足时，Z3 会修改模型吗？ 如果是这样，我该如何使用 C++ api?

非常感谢，

如果求解器 returns "sat"，您可以检索模型。该模型指的是求解器的状态，因此如果您添加断言，状态更改和模型将不再有效，直到您检查可满足性并且它 returns 满足。 因此，您可以在求解器每次 returns SAT 时检索一个模型，然后将除最后一个模型之外的所有模型都排出。

正如 Nikolaj 所提到的，您需要在每次调用后跟踪模型，如果您遵循该策略，则每次调用都会导致 sat 和 return 最后一次调用时获得 unsat你概述了。

但是，可能还有另一种替代方法可以完全避免重复调用。您可以将问题转化为优化问题，而不是满意度问题。您提到您有控制变量 b0、b1、.. bn，因此您希望最小化设置为 true 的变量数量以获得令人满意的模型。创建一个指标来计算这些变量中的个数。类似于：

metric = (if b0 then 1 else 0)
       + (if b1 then 1 else 0)
       + ...
       + (if bn then 1 else 0)

然后使用Z3的优化例程来最小化metric。我相信这将在一个电话中为您提供您正在寻找的解决方案。

一些有用的参考资料：