如何让 z3 达到 return 多个 unsat 核心，多个令人满意的分配

Question

我正在研究一个研究工具的组件；我有兴趣检索（QF_LRA）

-多个（最小或其他）UNSAT 核心和
-多项 SAT 作业

我已经在论坛上查看过有关此主题的早期讨论，例如， How to get different unsat cores when using z3 on logic QF_LRA

他们参考了 z3 Python 教程例如，http://rise4fun.com/Z3Py/tutorial/musmss

目前似乎处于离线状态。我已经尝试了 github 等的其他建议来找到提到的教程，但没有运气。

我正在使用 z3 Java API；但很高兴改用替代品。

Answer 1

这是教程。您可以在 MARCO 上找到更多信息来自 Mark Liffiton 的网页。

最小不可满足核和最大满足子集的枚举

本教程说明了如何使用 Z3 提取所有最小不可满足的核心连同所有最大满足子集。

来源

我们接下来描述的算法代表 Liffiton 和 Malik 独立提取岩心程序的本质通过 Previti 和 Marques-Silva:

枚举不可行：快速查找多个MUS
马克·H·利菲顿和阿马尔·马利克
在 过程中。第10^届国际人工智能集成会议约束规划中的智能 (AI) 和运筹学 (OR) 技术 (CPAIOR-2013)，160-175，2013 年 5 月。

部分 MUS 枚举
亚历山德罗·普雷维蒂，若昂 Marques-Silva 在 过程中。 AAAI-2013 2013 年 7 月

Z3py 功能

此实现不包含调整。它由 Mark Liffiton 提供，是对可用版本之一的简化他的马可波罗网站。 eMUS 的代码也可用。该示例说明了 Z3 的 Python-based API 的以下功能：

使用假设来追踪不可满足的核心。
使用多个求解器并在它们之间传递约束。
从 Python 调用 C-based API。 Python 并非支持所有 API 函数包装纸。此示例显示如何获取 AST 的唯一整数标识符，可以用作 hash-table 中的键。

算法思路

算法的主要思想是维护两个逻辑上下文和它们之间的信息交换：

MapSolver 用于枚举还没有的子句集现有不可满足核心的超集，并且还不是最大令人满意分配的子集。 MapSolver 每个 soft 子句使用一个唯一的原子谓词，因此它枚举原子谓词集。对于每个最小的不可满足的核心，比如说，由谓词表示 p₁、p₂、p₅、 MapSolver 包含子句 ¬ p₁ ∨ ¬ p₂ ∨ ¬ p₅. 对于每个最大可满足子集，例如，由谓词表示 p₂、p₃、p₅、 MapSolver 包含一个子句对应于所有文字的析取不在最大可满足子集中，p₁ ∨ p₄ ∨ p₆ 。
SubsetSolver 包含一个集合软子句（具有唯一指示原子出现的子句被否定的子句）。 MapSolver 为它提供一组子句（指示原子）。回想一下，这些还不是现有最小值的超集不可满足的核心，或最大令人满意的分配的子集。如果断言这些原子使 SubsetSolver 上下文不可行，然后它找到与这些原子对应的最小不可满足子集。如果断言原子与 SubsetSolver 一致，则它将这组原子最大限度地扩展到一个令人满意的集合。

from Z3 import *

def main():
    x, y = Reals('x y')
    constraints = [x > 2, x < 1, x < 0, Or(x + y > 0, y < 0), Or(y >= 0, x >= 0), Or(y < 0, x < 0), Or(y > 0, x < 0)]
    csolver = SubsetSolver(constraints)
    msolver = MapSolver(n=csolver.n)
    for orig, lits in enumerate_sets(csolver, msolver):
        output = "%s %s" % (orig, lits)
        print(output)



def get_id(x):
    return Z3_get_ast_id(x.ctx.ref(),x.as_ast())

def MkOr(clause):
    if clause == []:
       return False
    else:
       return Or(clause)

子集求解器：

class SubsetSolver:
   constraints = []
   n = 0
   s = Solver()
   varcache = {}
   idcache = {}

   def __init__(self, constraints):
       self.constraints = constraints
       self.n = len(constraints)
       for i in range(self.n):
           self.s.add(Implies(self.c_var(i), constraints[i]))

   def c_var(self, i):
       if i not in self.varcache:
          v = Bool(str(self.constraints[abs(i)]))
          self.idcache[get_id(v)] = abs(i)
          if i >= 0:
             self.varcache[i] = v
          else:
             self.varcache[i] = Not(v)
       return self.varcache[i]

   def check_subset(self, seed):
       assumptions = self.to_c_lits(seed)
       return (self.s.check(assumptions) == sat)

   def to_c_lits(self, seed):
       return [self.c_var(i) for i in seed]

   def complement(self, aset):
       return set(range(self.n)).difference(aset)

   def seed_from_core(self):
       core = self.s.unsat_core()
       return [self.idcache[get_id(x)] for x in core]

   def shrink(self, seed):       
       current = set(seed)
       for i in seed:
          if i not in current:
             continue
          current.remove(i)
          if not self.check_subset(current):
             current = set(self.seed_from_core())
          else:
             current.add(i)
       return current

   def grow(self, seed):
       current = seed
       for i in self.complement(current):
           current.append(i)
           if not self.check_subset(current):
              current.pop()
       return current

地图求解器：

class MapSolver:
    def __init__(self, n):
        """Initialization.
           Args:
            n: The number of constraints to map.
        """
       self.solver = Solver()
       self.n = n
       self.all_n = set(range(n))  # used in complement fairly frequently

   def next_seed(self):
       """Get the seed from the current model, if there is one. 
            Returns:
            A seed as an array of 0-based constraint indexes.
       """
       if self.solver.check() == unsat:
            return None
       seed = self.all_n.copy()  # default to all True for "high bias"
       model = self.solver.model()
       for x in model:
           if is_false(model[x]):
              seed.remove(int(x.name()))
       return list(seed)

   def complement(self, aset):
       """Return the complement of a given set w.r.t. the set of mapped constraints."""
       return self.all_n.difference(aset)

   def block_down(self, frompoint):
       """Block down from a given set."""
       comp = self.complement(frompoint)
       self.solver.add( MkOr( [Bool(str(i)) for i in comp] ) )

   def block_up(self, frompoint):
       """Block up from a given set."""
       self.solver.add( MkOr( [Not(Bool(str(i))) for i in frompoint] ) )



  def enumerate_sets(csolver, map):
      """Basic MUS/MCS enumeration, as a simple example."""
      while True:
        seed = map.next_seed()
        if seed is None:
           return
        if csolver.check_subset(seed):
           MSS = csolver.grow(seed)
           yield ("MSS", csolver.to_c_lits(MSS))
           map.block_down(MSS)
        else:
           MUS = csolver.shrink(seed)
           yield ("MUS", csolver.to_c_lits(MUS))
           map.block_up(MUS)

   main()

如何让 z3 达到 return 多个 unsat 核心，多个令人满意的分配

How to get z3 to return multiple unsat cores, multiple satisfying assignments

z3

smt

sat

最小不可满足核和最大满足子集的枚举

来源

Z3py 功能

算法思路