如何在Z3-Python中使用软约束来表达SAT搜索中的'abstract'偏差：如'I prefer half of the literals to be true and half false'

Question

我之前在中问过，在 Z3 (Python) 中是否有办法 'bias' SAT 搜索 'criteria'？

在那post中，我们学习了'simple biases'例如我希望Z3获得一个模型，但不是任何模型：if possible,给我一个有大量否定字面量的模型

这是使用新求解器（Optimize 而不是 Solver）和软约束（add_soft 而不是 add）执行的。具体来说，对于每个文字 lit_n 和优化求解器 o_solver，添加了：o_solver.add_soft(Not(lit_n))；或者，等价地：o_solver.add_soft(Or(Not(lit1), Not(lit2), ...).

不过，我想表达一个'little more complicated biases'。具体来说：如果可能：我更喜欢一半文字的模型为真，一半为假 .

有什么方法可以使用 Optimize 工具来表达这个和类似的 'biases'？

Answer 1

这里有一个可能有用的简单想法。计算正文字的数量并从负文字的数量中减去。取差异的绝对值并使用优化器将其最小化。

这应该找到正负文字数量尽可能接近的解决方案，满足您的“大约一半”软约束。

这是一个简单的例子。假设您有六个文字并且您想要满足它们的析取。惯用的解决方案是：

from z3 import *

a, b, c, d, e, f = Bools("a b c d e f")

s = Solver()
s.add(Or(a, b, c, d, e, f))

print(s.check())
print(s.model())

如果你运行这个，你会得到：

sat
[f = False,
 b = False,
 a = True,
 c = False,
 d = False,
 e = False]

所以，z3 只是让 a True 和所有其他 False。但是您希望正面和负面文字的数量大致相同。那么，让我们对其进行编码：

from z3 import *

a, b, c, d, e, f = Bools("a b c d e f")

s = Optimize()
s.add(Or(a, b, c, d, e, f))

def count(ref, xs):
    s = 0
    for x in xs:
        s += If(x == ref, 1, 0)
    return s

def sabs(x):
    return If(x > 0, x, -x)

lits = [a, b, c, d, e, f]
posCount = count(True,  lits)
negCount = count(False, lits)
s.minimize(sabs(posCount - negCount))


print(s.check())
print(s.model())

注意我们如何“象征性地”计算负文字和正文字并要求 z3 最小化差异的绝对值。如果你运行这个，你会得到：

sat
[a = True,
 b = False,
 c = False,
 d = True,
 e = False,
 f = True]

有 3 个正字面量和 3 个负字面量。如果您有 7 个文字开始，它会发现 4-3 拆分。如果您更喜欢正文字而不是负文字，则可以另外添加以下形式的软约束：

s.add_soft(posCount >= negCount)

以这种方式偏置求解器。希望这能让你开始..

如何在Z3-Python中使用软约束来表达SAT搜索中的'abstract'偏差：如'I prefer half of the literals to be true and half false'

How to use soft constraints in Z3-Python to express 'abstract' biases in SAT search: such as 'I prefer half of the literals to be true and half false'

z3

z3py

theorem-proving

sat

satisfiability