在 Z3 中编码 max、min 和 abs 的最有效方式

Question

我有一个我想解决的非线性整数不等式系统。在其中我需要计算整数的绝对值以及两个整数的 maximum/minimum。

这是一个玩具示例：

from z3 import *
set_option(verbose=10)
x, y, z, z1 = Ints('x y z z1')
def abs(x):
    return If(x >= 0,x,-x)

def max(x, y):
    return If(x>=y, x, y)

def min(x, y):
    return If(x<=y, x, y)

s = Solver()

s.add(x**2 + y**2 >= 26)
s.add(min(abs(y), abs(x))> 5)
s.add(3*x**2 + 25*y**2 >= 100)
s.add(x*y - z*z1 < 10)
s.add(max(abs(z), abs(z1)) <= 10)
s.add(min(abs(z), abs(z1)) > 1)
s.check()
print(s.model())

我的真实系统更复杂，需要更长的时间才能运行。

我不太明白 Z3 是如何工作的，但我担心我使用 Python 定义 abs、max 和 min 的方式函数可能会使 Z3 难以求解不等式系统。有没有更好的方法可以让 Z3 更有效率？

Answer 1

您的编码方式很好。确实没有“更好”的方法来编写这些操作。

非线性问题对于 SMT 求解器来说真的很难。事实上，他们解决这些问题的一种方法是假设这些值是“实”数，解决它，然后检查模型是否实际上只包含整数。另一个技巧是减少到位向量：将越来越大的位向量分配给变量，看看是否可以找到模型。您可以想象这两种技术都适合“模型发现”，但在证明 unsat 方面却很糟糕。（详情见：How does Z3 handle non-linear integer arithmetic?）

如果您的问题确实是非线性的，那么 SMT 求解器可能不是最适合您的工具。支持算术理论的实际定理证明器可能是更好的选择，当然这是一个完全不同的讨论。

您可以尝试的一件事是“简化”问题。例如，您似乎总是使用 abs(y) 和 abs(x)，也许您可以删除 abs 术语并简单地断言 x > 0 和 y > 0？请注意，这不是降噪：您是明确告诉求解器忽略所有负面 x 和 y值，但它可能足以解决您的问题，因为您可能只关心 x 和 y 无论如何都是正的。这将有助于求解器，因为它会减少搜索 space 并摆脱条件表达式，但请记住，您在问一个不同的问题，因此您的解决方案 -space 现在不同了. （它甚至可能变成 unsat 新约束。）

长话短说；非线性算术很困难，您编码 min/max/abs 的方式很好。看看你是否可以通过不使用它们来“简化”问题，或许可以为求解器解决一个相关的更简单的问题。如果那不可能，恐怕您将不得不超越 SMT 求解器来处理您的非线性方程组。（而且 none 当然会很容易，因为这个问题本身就很困难。再次通读 How does Z3 handle non-linear integer arithmetic? 以获得一些额外的细节。）

在 Z3 中编码 max、min 和 abs 的最有效方式

The most efficient way to encode max, min and abs in Z3

python

z3