修改 Z3 中的分而治之 SAT 搜索-Python

Question

我正在尝试修改 Z3 中的分而治之 SAT 搜索 (Python)，但感觉完全迷失了。我会分三部分解释我的问题。

简介

我在 Z3 中使用其默认增量选项（即使用 add）执行 SAT 搜索循环。

然而，我知道我的搜索是一个简单的枚举类型“找到我所有的解决方案”，它包括“添加先前模型的否定并迭代”。像下面这样：

  ...
  phi = a_formula
  s = Solver()
  s.add(phi)
  while  s.check() == sat: 
    s.check()
    m = s.model()
    phi = add_modelNegation(m)
    s.add(phi) #in order not to explore the same model again
  ...

这显然是一个 'brute-force' 实现。

我还注意到，为了加快搜索速度，我可以使用“分而治之”的方法来代替它。为此，我得到了以下 link (Z3Py) checking all solutions for equation (see the last answer by @alias). I tested this code works at 。代码实质如下：

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))

问题

我的 SAT 问题不是 'basic' 我只是列举（或快速列举，如果我按照上面的代码）所有解决方案的问题。我有一个 'booster' 允许我在给定模型具有某些属性时添加更多限制。这个助推器是一种启发式的。架构如下：

  ...
  s = Solver()
  s.add(True)
  while  s.check() == sat: 
    s.check()
    m = s.model()
    phi = add_modelNegation(m)
    s.add(phi) #in order not to explore the same model again
    if holds_property(m): #if the model holds a property
       add_moreConstraints(s,m) #add other constrains to the formula
  ...

我想在这个版本中加入all_smt的想法，准确地利用push和pop。我的问题是我不完全理解 push 和 pop 的用法，并且由于我的代码不像快速代码那样修复变量，所以我不知道如何 'merge' 两者想法。我怎样才能使我的代码更快？

一个具体的编码例子：

下面我举一个具体的例子。这是为了方便大家打码而做的例子，实际没有意义。

例如，假设助推器或启发式是如果模型中错误分配的数量大于 1，那么我们可以将 'reversed' 模型添加到求解器，其中 'reversed' 模型只是将每个分配的值更改为相反的值。例如，如果模型是 phi=[c0=True, c1=False, c2=False, c3=True]，那么 phi 包含属性，因此，它的 'reverse' 被添加，其中 phi_reversed = [c0=False, c1=True, c2=True, c3=False]。另一方面，phi'=[c0=True, c1=True, c2=False, c3=True] 不包含属性，因此不会向求解器添加任何额外内容。

我再说一遍，这个助推器没有任何意义，但为了编码就足够了。因此，让我们创建该函数：

def holds_property(m, varss):
    numFalses = 0
    for x in varss:
       if m[x] == False:
         numFalses = numFalses + 1
    if numFalses > 1:
       return True
    else:
       return False

还有创建模型 'reversed' 版本的函数：

def make_reverse(m, varss):
    for x in varss:
       if m[x] == True:
          m[x] = False
       elif m[x] == False:
          m[x] = True
    return m

我也会发明一个公式和一组变量。因此，我的 'brute-force' 实现是（这不是伪代码）：

  a,b,c = Bools('a b 'c)
  varss = [a,b,c]
  phi = And(a, Or(b,c))
  s = Solver()
  s.add(phi)
  models = []
  while  s.check() == sat: 
    s.check()
    m = s.model()
    models.append(m)
    phi = add_modelNegation(m)
    s.add(phi)
    if holds_property(m, varss):
       s.add(make_reverse(m, varss))
  return models

问题又来了：如何将 'fast' 版本的思想插入（或修改）到这个版本中？我想用 push 和 pop 添加 'fixing'，基本上。

有什么帮助吗？我知道这个问题很复杂，但我试着冷静地用例子来解释它:) 不管怎样，不要犹豫，问更多，我会编辑 post.

Answer 1

当您 push 时，您正在您的断言中创建一个嵌套级别。也就是说，求解器在断言堆栈上放置一个标记，稍后您可以通过调用 pop 跳回该堆栈。当然，这意味着当您执行 pop 时，您将丢失在最后一个 push.

之后插入的所有断言

由于您有 额外约束，只需跟踪它们，并在调用 push 和 pop 之间管理它们。像这样：

from z3 import *

def pruned_all_smt(s, initial_terms, holds_property, more_constraints):

    global extra_constraints

    extra_constraints = []

    def block_term(m, t):
        s.add(t != m.eval(t, model_completion=True))

    def fix_term(m, t):
        s.add(t == m.eval(t, model_completion=True))

    def custom_pop():
        global extra_constraints

        s.pop()
        for ec in extra_constraints:
            s.add(ec)

    def custom_model():
        global extra_constraints

        m = s.model()

        if holds_property(m):
            extra_constraints = more_constraints(m) + extra_constraints

        for ec in extra_constraints:
            s.add(ec)

        return m

    def pruned_all_smt_rec(terms):
        if sat == s.check():
           m = custom_model()
           yield m
           for i in range(len(terms)):
               s.push()
               block_term(m, terms[i])
               for j in range(i):
                   fix_term(m, terms[j])
               yield from pruned_all_smt_rec(terms[i:])
               custom_pop()

    yield from pruned_all_smt_rec(list(initial_terms))

请注意，我们制作了 hold_property 和 more_constraint 参数，因此您需要单独提供这些参数。这是一个模板使用：

def check_prop(m):
    return True;

def more_constraints(m):
    return []

鉴于此，您可以将其用作：

print(list(pruned_all_smt(s, varss, check_prop, more_constraints)))

试一试，看看你能走多远。我还没有用任何有意义的东西真正测试过它，所以可能会有一些问题！

修改 Z3 中的分而治之 SAT 搜索-Python

Modifying the divide and conquer SAT search in Z3-Python

theorem-proving

divide-and-conquer

z3

z3py

sat