如何检查 1000 多个没有重复值的变量？

Question

我是 Z3 的新手，对于一个开源程序，我想使用 z3 求解器来提高效率。

我有大约 1000 多个值

(declare-const a1 Int)
(declare-const a2 Int)
(declare-const a3 Int)
(declare-const a4 Int)
...

哪个结果

(declare-const x1 Int)
(declare-const x2 Int)
...
(assert (=  (+ a1 a2) x1) // in reality its not "plus" but more sophisticated
(assert (=  (+ a3 a4) x2) // however for simplicity lets keep it at that here.
...

现在我要确保所有 x1 到 x500+ 变量都具有不同的值并且没有重复项。

当然可以

(assert (not (= x1 x2)))
(assert (not (= x1 x3)))
(assert (not (= x1 x4)))
...
(assert (not (= x2 x3)))
(assert (not (= x2 x4)))
...
(assert (not (= x718 719)))

这可行 - 但有更好的解决方案吗？

非常感谢！

Answer 1

您可以使用 distinct（参见 example）：

(assert (distinct x1 ... x500))

据我所知，这通常会在内部扩展为一系列不等式，就像您在示例中展示的那样。

讨论：以下是关于这种编码效率的纯理论讨论； z3 是一个非常有效的 SMT 求解器，因此您可能不需要尝试任何比运行工具更复杂的东西。

等式的否定（例如(not (= x y))）通常分为一对不等式：

x < y \/ x > y

假设 x < y 和 x > y 分别重命名为 B1 和 B2，将以下子句提供给 SAT 引擎：

B1 \/ B2

现在，鉴于您的问题，您会得到数百个这样的子句。这些都在线性算术级别相互关联，但在 SAT 引擎运行的布尔级别不相关。因此，SAT 引擎可能会生成（大量）不一致的部分真值分配，这通常会违反 < 运算符的传递性属性，例如

 x < y /\ y < z /\ z < x

LRA 的理论求解器将在 早期修剪 调用期间揭示这些冲突，并通过学习阻止无效分配的冲突子句在布尔级别解决。

你可以尝试什么：

如果您的问题允许这样的简化（如果 x1 ... x500 的名称可能被认为是完全随意的，之后可以将它们打乱..），你可能会得到更好的结果，对变量 x1 ... x500 施加严格的总顺序，例如
```
x1 < x2 /\ x2 < x3 /\ ... /\ x499 < x500
```
您可以尝试使用 z3 增加 早期修剪 调用的频率，如果这是一个可用选项 （注意: 我不确定 z3 执行此类调用的频率)
你可以尝试 mcSAT 可能会很好地处理这种限制。

编辑：

如果可以分配给变量 x_i 的值集是有限的并且在大小上有所限制，您可以尝试使用非-用于定义基数约束的标准 z3 扩展，例如

(assert
    ((_ at-most 1)
     (= x1 0)
     (= x2 0)
     ...
     (= x500 0)
    )
)
...
% repeat for all possible values 
...

我不确定此更改对性能的影响。在正常情况下，它会对性能产生积极影响，因为它会更早地揭示冲突分配（参见，例如，[1]）。但是，您正在处理大量变量和变量的大量候选值域 x_i，因此在布尔级别展开搜索可能有点矫枉过正。

如何检查 1000 多个没有重复值的变量？

How to check for 1000+ variables having no duplicate values?

z3