Z3PY 非常慢，有很多变量？

Question

我一直在使用 Z3PY 中的优化器，并且在我的项目中只使用 Z3 整数和 (x < y)-like 约束。它真的很有效。我一直在使用多达 26 个变量（Z3 整数），求解器需要大约 5 秒才能找到解决方案，而且我至少有 100 个软约束。但是现在我尝试了 49 个变量，它根本没有解决它（我在 1 小时后关闭它）。所以我做了一个小实验来找出是什么让它变慢了，是变量的数量还是软约束的数量？瓶颈似乎是变量的数量。

我创建了 26 个 Z3-int。然后我添加了硬约束，即它不应低于 1 或超过 26。此外，所有数字都必须是唯一的。根本没有添加其他约束。换句话说，求解器将找到的解决方案是一个简单的顺序 [1,2,3,4,5.... 最多 26]。以求解器发现的方式排序。

我的意思是这是一件简单的事情，除了我提到的那些之外，真的没有任何限制。求解器在 0.4 秒或类似的时间内解决了这个问题，速度快且足够。这是预期的。但是如果我将变量的数量增加到 49（当然现在的约束是不能低于 1 或超过 49），求解器需要大约 1 分钟的时间来求解。对于这样一个简单的任务来说，这似乎真的很慢？应该是这样的，有人知道吗？时间复杂度真的大大增加了？

（我知道我可以使用 Solver() 而不是 Optimizer() 来进行这个特定的实验，它会在一秒钟内解决，但实际上我需要用 Optimizer 来完成，因为我有很多要使用的软约束。）

编辑：为我的示例添加一些代码。

I declare an array with Z3 ints that I call "reqs".
The array is consisting of 26 variables in one example and 49 in the other example I am talking about.

solver = Optimize()

 for i in (reqs):
     solver.add(i >= 1)

for i in (reqs):
    solver.add(i <= len(reqs))

    d = Distinct(reqs)
    solver.add(d)

res = solver.check()
print(res)

Answer 1

每个基准都是独一无二的，不可能想出一个适用于所有情况的好策略。但是您描述的场景很简单，可以处理。性能问题来自这样一个事实，即 Distinct 为求解器创建了太多不等式（数量的二次方），并且随着变量数量的增加，优化器很难处理它们。

根据经验，您应该尽可能避免使用 Distinct。对于这种特殊情况，对变量施加严格的排序就足够了。（当然，这可能并不总是可行，具体取决于您的其他限制，但您所描述的似乎可以从这个技巧中受益。）所以，我会这样编码：

from z3 import *

reqs = [Int('i_%d' % i) for i in range(50)]

solver = Optimize()

for i in reqs:
  solver.add(i >= 1, i <= len(reqs))

for i, j in zip(reqs, reqs[1:]):
  solver.add(i < j)

res = solver.check()
print(res)
print(solver.model())

当我运行这个时，我得到：

$ time python a.py
sat
[i_39 = 40,
 i_3 = 4,
 ...
 i_0 = 1,
 i_2 = 3]
python a.py  0.27s user 0.09s system 98% cpu 0.365 total

这很狡猾。希望您可以将其推广到您的原始问题。

Z3PY 非常慢，有很多变量？

Z3PY extremely slow with many variables?

z3

solver

smt

z3py