z3 比 ortools SAT 慢得多。为什么？

Question

我正在为一个玩具尝试不同的求解器 clique problem and was surprised to find that ortools using SAT seems much faster than z3。鉴于 z3 在已发布的基准测试中表现如此出色，我想知道我是否做错了什么。这是一个 MWE：

首先创建一个有150个顶点的随机图：

# First make a random graph and find the largest clique size in it
import igraph as ig
import random
from tqdm import tqdm
random.seed(7)
num_variables = 150  # bigger gives larger running time gap between z3 and ortools grow
print("Making graph")
g = ig.Graph.Erdos_Renyi(num_variables, 0.6)

# Make a set of edges. Maybe this isn't necessary
print("Making set of edges")
edges = set()
for edge in tqdm(g.es):
    edges.add((edge.source, edge.target))

现在使用 z3 查找最大 clique 大小：

import z3
z3.set_option(verbose=1)
myVars = []
for i in range(num_variables):
    myVars += [z3.Int('v%d' % i)]

opt = z3.Optimize()

for i in range(num_variables):
    opt.add(z3.Or(myVars[i]==0, myVars[i] == 1))

for i in tqdm(range(num_variables)):
    for j in range(i+1, num_variables):
        if not (i, j) in edges:
            opt.add(myVars[i] + myVars[j] <= 1)

t = time()
h = opt.maximize(sum(myVars))
opt.check()
print(round(time()-t,2))

这在我的 PC 上大约需要 70 秒。

现在使用 ortools 中的 SAT 做同样的事情。

from ortools.linear_solver import pywraplp
solver = pywraplp.Solver.CreateSolver('SAT')
solver.EnableOutput()

myVars = []

for i in range(num_variables):
        myVars += [solver.IntVar(0.0, 1.0, 'v%d' % i)]

for i in tqdm(range(num_variables)):
    for j in range(i+1, num_variables):
        if not (i, j) in edges:
            solver.Add(myVars[i] + myVars[j] <= 1)

print("Solving")
solver.Maximize(sum(myVars))
t = time()
status = solver.Solve()
print(round(time()-t,2))

这在我的 PC 上大约需要 4 秒。

如果你增加 num_variables 差距会变得更大。

我是不是做错了什么，或者这对 z3 优化器来说真的很糟糕吗？

更新

事实证明，使用 SAT 的 ortools 是多核的，默认情况下使用 8 个内核，因此时序不公平。使用@AxelKemper 的改进我现在得到（在另一台机器上）：

Z3时间88秒。如果我们假设 8 个核心上的完美并行化为 11 秒。
ortools 4.3 秒

因此 Z3 仅比 ortools 慢 2.5 倍。

更新 2

使用@alias 的改进代码，该代码使用 s.add(z3.PbGe([(x, 1) for x in myVars], k)) 现在需要 30.4 秒，除以 8 比 ortools 更快！

Answer 1

将 Int 变量替换为 Bool 变量将我机器上的 z3py 运行时间减少了 28%：

z3.set_option(verbose=1)
myVars = []
for i in range(num_variables):
    myVars += [z3.Bool('v%d' % i)]   #  Bool rather than Int

opt = z3.Optimize()
   
for i in tqdm(range(num_variables)):
    for j in range(i+1, num_variables):
        if not (i, j) in edges:
            opt.add(Not(And(myVars[i], myVars[j])))

t = time()
h = opt.maximize(Sum([If(myVars[i], 1, 0) for i in range(num_variables)]))
opt.check()
print(round(time()-t,2))

Answer 2

像 ortools 这样的自定义工具通常很难被击败，因为它只理解固定数量的域，并且它们利用了并行硬件。 SMT 求解器的亮点不在于速度，而在于它所允许的：许多理论（算术、data-structures、布尔值、实数、整数、浮点数等）的组合，因此这不是一个公平的比较。

话虽如此，我们可以通过三个想法让 z3 运行得更快：

使用 Bool 而不是 Axel 建议的 Int。 z3 按原样处理布尔值要好得多，而不是通过整数对它们进行编码。有关在 z3 中编码的一般建议，请参阅 this earlier answer。
z3 的常规求解器比优化器更擅长处理许多约束。虽然优化器肯定有它的应用程序，但如果可以的话，请避免使用它。如果您的问题可以使用迭代方法（即获得解决方案并通过添加新约束不断改进），那绝对值得尝试。当然，并非所有优化问题都适用于这种基于迭代的优化，但只要适用，它就可以带来回报。（其中一个原因是优化是一个更困难的问题，可能会使求解器陷入无关紧要的细节。第二个原因是与求解器引擎相比，z3 的优化器近年来没有受到太多关注，所以它不是跟上对主线求解器所做的改进。至少这是我的印象。）
使用 pseudo-boolean 等式，z3 有内部策略可以更有效地处理。对于 pseudo-boolean 约束，see this answer.

将所有这些想法放在一起，这就是我在 z3 中对您的问题进行编码的方式：

import igraph as ig
import random
from time import *
import z3

# First make a random graph and find the largest clique size in it
from tqdm import tqdm
random.seed(7)
num_variables = 150  # bigger gives larger running time gap between z3 and ortools grow
print("Making graph")
g = ig.Graph.Erdos_Renyi(num_variables, 0.6)

# Make a set of edges. Maybe this isn't necessary
print("Making set of edges")
edges = set()
for edge in tqdm(g.es):
    edges.add((edge.source, edge.target))

myVars = []
for i in range(num_variables):
    myVars += [z3.Bool('v%d' % i)]

total = sum([z3.If(i, 1, 0) for i in myVars])

s = z3.Solver()
for i in tqdm(range(num_variables)):
    for j in range(i+1, num_variables):
        if not (i, j) in edges:
            s.add(z3.Not(z3.And(myVars[i], myVars[j])))

t = time()
curTotal = 0
while True:
  s.add(z3.PbGe([(x, 1) for x in myVars], curTotal+1))
  r = s.check()
  if r == z3.unsat:
      break
  curTotal = s.model().evaluate(total, model_completion=True).as_long()
  print(r, curTotal, round(time()-t,2))

print("DONE total time =", round(time()-t,2))

请注意 z3.PbGe 的使用，它引入了 pseudo-boolean 约束。在我的实验中，它比常规约束版本运行得更快；如果您还假设 8 核完全并行化 speed-up，我认为它比 ortools 解决方案更有优势。

请注意，上面的迭代循环是以线性方式编码的，即，我们要求 curTotal+1 解决方案，每次调用 check 时，z3 找到的最后一个解决方案仅递增 1。以一些额外的编程为代价，您还可以实现类似 binary-search 的例程，即要求最后结果的两倍，如果 unsat 缩小以找到最佳值，则使用 push /pop 来管理断言堆栈。当分摊到多次运行时，这个技巧可以表现得更好。

请报告你自己的实验结果！

z3 比 ortools SAT 慢得多。为什么？

z3 much slower than ortools SAT. Why?

python

z3

or-tools

z3py

sat