使用 z3py 中的 Optimize() 找到所有最优解

Question

z3 可以使用 z3.Optimize 解决优化问题。我的目标是按以下方式应用它：给定命题逻辑的布尔公式和一组约束，找到所有优化约束的模型，即尽可能多地满足。我的最终目标是 select 随机选择其中一个模型。

最小示例：给定公式 Or(x,y) 和约束条件 Not(x) 和 Not(y)，找到解决方案 [x: True, y: False] 和 [x: False, y: True]。

虽然 z3.Optimize.model() 打印了一个最佳解决方案，但它似乎是确定性的并且总是打印解决方案 [x: False, y: True]:

from z3 import *

x, y = Bools('x y')
s = Optimize()
s.add(Or(x,y))
s.add_soft(Not(x), weight="1")
s.add_soft(Not(y), weight="1")
s.check()
print(s.model())

将@alias提供的all_smt()应用到这个问题上，list(all_smt(s, [x,y]))输出：

[[x = False, y = True], [y = False, x = True], [y = True, x = True]]

所以all_smt()找到所有解，包括非最优解[x: True, y: True]。

找到所有最优解的最佳方法是什么？或者，是否可以在不先生成所有最优解的情况下以随机方式找到最优解？

Answer 1

在这种情况下，您所说的“最佳”不是很清楚。看来您允许 soft-constraints 被违反，但至少其中一个必须成立？（毕竟，（[x=True, y=True] 是一个有效的解决方案，违反了您的 soft-constraints；您确实通过显式调用 all_smt 允许了这一点。）

假设您确实正在寻找至少满足 soft-constraints 之一的解决方案，您应该明确地将其编码并断言为一个单独的谓词。最简单的方法是使用跟踪器变量：

from z3 import *

def all_smt(s, initial_terms):
    def block_term(s, m, t):
        s.add(t != m.eval(t, model_completion=True))
    def fix_term(s, m, t):
        s.add(t == m.eval(t, model_completion=True))
    def all_smt_rec(terms):
        if sat == s.check():
           m = s.model()
           yield m
           for i in range(len(terms)):
               s.push()
               block_term(s, m, terms[i])
               for j in range(i):
                   fix_term(s, m, terms[j])
               yield from all_smt_rec(terms[i:])
               s.pop()
    yield from all_smt_rec(list(initial_terms))

x, y = Bools('x y')
s = Optimize()

s.add(Or(x,y))

p1, p2 = Bools('p1 p2')
s.add(Implies(p1, Not(x)))
s.add(Implies(p2, Not(y)))

asserted = If(p1, 1, 0) + If(p2, 1, 0)
s.add(asserted >= 1)
s.minimize(asserted)

print([[(x, m[x]), (y, m[y])] for m in all_smt(s, [x,y])])

这里，我们使用p1和p2来跟踪soft-constraints是否断言，我们通过变量[=16=来最小化soft-constraints的数量] 但要求它至少应该是 1。当运行时，上面打印：

[[(x, True), (y, False)], [(x, False), (y, True)]]

这似乎是您最初想要实现的目标。

使用 z3py 中的 Optimize() 找到所有最优解

Find all optimal solutions with Optimize() from z3py

python

z3

z3py