如何将 Z3 的 (Python) SAT 解决方案偏向一个标准，例如 'preferring' 以获得更多否定文字
How to bias Z3's (Python) SAT solving towards a criteria, such as 'preferring' to have more negated literals
在 Z3 (Python) 中，有什么方法可以 'bias' SAT 搜索 'criteria' 吗？
一个案例：我希望Z3获得一个模型，但不是任何模型：如果可能，给我一个具有大量否定文字的模型。
因此，例如，如果我们必须搜索 A or B，可能的模型是 [A = True, B = True]，但我宁愿收到模型 [A = True, B = False] 或模型 [A = False, B = True]，因为他们有更多 False 作业。
当然，我想 'criteria' 必须更具体（比如 如果可能：我更喜欢 half 文字的模型为 False ），但我认为这个想法是可以理解的。
我不关心这个方法是不是原生的。有帮助吗？
Z3py 具有优化求解器 Optimize. This has a method add_soft，描述如下：
添加带有可选权重和可选标识符的软约束。
如果没有提供重量，那么违反软约束的惩罚
是 1。
软约束按标识符分组。软约束是
没有标识符的添加默认分组。
可以找到一个小例子here:
Optimize 上下文为可满足性检查提供了三个主要扩展：
o = Optimize()
x, y = Ints('x y')
o.maximize(x + 2*y) # maximizes LIA objective
u, v = BitVecs('u v', 32)
o.minimize(u + v) # minimizes BV objective
o.add_soft(x > 4, 4) # soft constraint with
# optional weight
在 z3 中有两种主要的方法来处理这类问题。使用优化器，或通过多次调用求解器手动计算。
使用优化器
正如 Axel 指出的那样，处理此问题的一种方法是使用优化求解器。您的示例将编码如下：
from z3 import *
A, B = Bools('A B')
o = Optimize()
o.add(Or(A, B))
o.add_soft(Not(A))
o.add_soft(Not(B))
print(o.check())
print(o.model())
这会打印：
sat
[A = False, B = True]
您可以向软约束添加权重，这提供了一种在违反约束时关联惩罚的方法。例如，如果你想尽可能使 A 为真，但不太关心 B，那么你会将更大的惩罚与 Not(B):[=40 相关联=]
from z3 import *
A, B = Bools('A B')
o = Optimize()
o.add(Or(A, B))
o.add_soft(Not(A))
o.add_soft(Not(B), weight = 10)
print(o.check())
print(o.model())
这会打印：
sat
[A = True, B = False]
思考的方式如下：您要求 z3：
- 满足所有常规约束。 （即，您输入的
add）
- 尽可能多地满足软约束条件（即，您使用
add_soft 设置的约束条件）。如果无法找到满足所有条件的解决方案，则允许求解器“违反”他们，试图最小化所有违反约束的总成本，通过对权重求和来计算。
- 当没有给出权重时，您可以假设它是
1。您也可以对这些约束进行分组，但我怀疑您是否需要这种普遍性。
因此，在第二个示例中，z3 违反了 Not(A)，因为这样做的成本为 1，而违反 Not(B) 的成本为 [=23] =].
请注意，当您使用优化器时，z3 使用的引擎与它用于常规 SMT 求解的引擎不同：特别是，该引擎是 而非 增量引擎。也就是说，如果您对其调用 check 两次（在引入一些新约束之后），它将从头开始解决整个问题，而不是从第一次的结果中学习。此外，优化求解器不像常规求解器那样 optimized（双关语！），因此它通常在直接可满足性方面也表现较差。有关详细信息，请参阅 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-nuz.pdf。
手动方法
如果您不想使用优化器，您也可以使用跟踪变量的想法“手动”执行此操作。这个想法是识别软约束（即可以以某种代价违反的约束），并将它们与跟踪器变量相关联。
基本算法如下：
列出您的软约束。在上面的示例中，它们将是 Not(A) 和 Not(B)。 （也就是说，您希望这些满足给您负文字，但显然您希望只有在可能的情况下才满足这些。）调用这些 S_i。假设您有 N 个。
对于每个这样的约束，创建一个新的跟踪器变量，它将是一个布尔值。调用这些 t_i.
为每个软约束断言 N 个常规约束，每个形式 Implies(t_i, S_i)。
使用形式为 AtMostK 的伪布尔约束来强制最多 K 这些跟踪器变量 t_i 为假。然后使用类似于模式的二进制搜索来找到 K 的最佳值。请注意，由于您使用的是常规求解器，因此可以在增量模式下使用它，即调用 push 和 pop.
有关此技术的详细说明，请参阅 。
总结
以上两种方法中哪一种有效取决于问题。从最终用户的角度来看，使用优化器是最简单的，但是您正在使用您可能不需要的重型机器，因此您可能会遭受性能损失。第二种方法可能更快，但存在更复杂（因此容易出错！）编程的风险。像往常一样，进行一些基准测试，看看哪种方法最适合您的特定问题。
在 Z3 (Python) 中，有什么方法可以 'bias' SAT 搜索 'criteria' 吗？
一个案例：我希望Z3获得一个模型，但不是任何模型：如果可能，给我一个具有大量否定文字的模型。
因此，例如，如果我们必须搜索 A or B，可能的模型是 [A = True, B = True]，但我宁愿收到模型 [A = True, B = False] 或模型 [A = False, B = True]，因为他们有更多 False 作业。
当然，我想 'criteria' 必须更具体（比如 如果可能：我更喜欢 half 文字的模型为 False ），但我认为这个想法是可以理解的。
我不关心这个方法是不是原生的。有帮助吗？
Z3py 具有优化求解器 Optimize. This has a method add_soft，描述如下：
添加带有可选权重和可选标识符的软约束。 如果没有提供重量，那么违反软约束的惩罚 是 1。 软约束按标识符分组。软约束是 没有标识符的添加默认分组。
可以找到一个小例子here:
Optimize 上下文为可满足性检查提供了三个主要扩展：
o = Optimize()
x, y = Ints('x y')
o.maximize(x + 2*y) # maximizes LIA objective
u, v = BitVecs('u v', 32)
o.minimize(u + v) # minimizes BV objective
o.add_soft(x > 4, 4) # soft constraint with
# optional weight
在 z3 中有两种主要的方法来处理这类问题。使用优化器，或通过多次调用求解器手动计算。
使用优化器
正如 Axel 指出的那样，处理此问题的一种方法是使用优化求解器。您的示例将编码如下：
from z3 import *
A, B = Bools('A B')
o = Optimize()
o.add(Or(A, B))
o.add_soft(Not(A))
o.add_soft(Not(B))
print(o.check())
print(o.model())
这会打印：
sat
[A = False, B = True]
您可以向软约束添加权重，这提供了一种在违反约束时关联惩罚的方法。例如，如果你想尽可能使 A 为真，但不太关心 B，那么你会将更大的惩罚与 Not(B):[=40 相关联=]
from z3 import *
A, B = Bools('A B')
o = Optimize()
o.add(Or(A, B))
o.add_soft(Not(A))
o.add_soft(Not(B), weight = 10)
print(o.check())
print(o.model())
这会打印：
sat
[A = True, B = False]
思考的方式如下：您要求 z3：
- 满足所有常规约束。 （即，您输入的
add） - 尽可能多地满足软约束条件（即，您使用
add_soft设置的约束条件）。如果无法找到满足所有条件的解决方案，则允许求解器“违反”他们，试图最小化所有违反约束的总成本，通过对权重求和来计算。 - 当没有给出权重时，您可以假设它是
1。您也可以对这些约束进行分组，但我怀疑您是否需要这种普遍性。
因此，在第二个示例中，z3 违反了 Not(A)，因为这样做的成本为 1，而违反 Not(B) 的成本为 [=23] =].
请注意，当您使用优化器时，z3 使用的引擎与它用于常规 SMT 求解的引擎不同：特别是，该引擎是 而非 增量引擎。也就是说，如果您对其调用 check 两次（在引入一些新约束之后），它将从头开始解决整个问题，而不是从第一次的结果中学习。此外，优化求解器不像常规求解器那样 optimized（双关语！），因此它通常在直接可满足性方面也表现较差。有关详细信息，请参阅 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-nuz.pdf。
手动方法
如果您不想使用优化器，您也可以使用跟踪变量的想法“手动”执行此操作。这个想法是识别软约束（即可以以某种代价违反的约束），并将它们与跟踪器变量相关联。
基本算法如下：
列出您的软约束。在上面的示例中，它们将是
Not(A)和Not(B)。 （也就是说，您希望这些满足给您负文字，但显然您希望只有在可能的情况下才满足这些。）调用这些S_i。假设您有N个。对于每个这样的约束，创建一个新的跟踪器变量，它将是一个布尔值。调用这些
t_i.为每个软约束断言
N个常规约束，每个形式Implies(t_i, S_i)。使用形式为
AtMostK的伪布尔约束来强制最多K这些跟踪器变量t_i为假。然后使用类似于模式的二进制搜索来找到K的最佳值。请注意，由于您使用的是常规求解器，因此可以在增量模式下使用它，即调用push和pop.
有关此技术的详细说明，请参阅 。
总结
以上两种方法中哪一种有效取决于问题。从最终用户的角度来看，使用优化器是最简单的，但是您正在使用您可能不需要的重型机器，因此您可能会遭受性能损失。第二种方法可能更快，但存在更复杂（因此容易出错！）编程的风险。像往常一样，进行一些基准测试，看看哪种方法最适合您的特定问题。