| 1 |
############################################ |
| 2 |
# Copyright (c) 2016 Microsoft Corporation |
| 3 |
# |
| 4 |
# Basic core and correction set enumeration. |
| 5 |
# |
| 6 |
# Author: Nikolaj Bjorner (nbjorner) |
| 7 |
############################################ |
| 8 |
|
| 9 |
""" |
| 10 |
Enumeration of Minimal Unsatisfiable Cores and Maximal Satisfying Subsets |
| 11 |
This tutorial illustrates how to use Z3 for extracting all minimal unsatisfiable |
| 12 |
cores together with all maximal satisfying subsets. |
| 13 |
|
| 14 |
Origin |
| 15 |
The algorithm that we describe next represents the essence of the core extraction |
| 16 |
procedure by Liffiton and Malik and independently by Previti and Marques-Silva: |
| 17 |
Enumerating Infeasibility: Finding Multiple MUSes Quickly |
| 18 |
Mark H. Liffiton and Ammar Malik |
| 19 |
in Proc. 10th International Conference on Integration of Artificial Intelligence (AI) |
| 20 |
and Operations Research (OR) techniques in Constraint Programming (CPAIOR-2013), 160-175, May 2013. |
| 21 |
|
| 22 |
Partial MUS Enumeration |
| 23 |
Alessandro Previti, Joao Marques-Silva in Proc. AAAI-2013 July 2013 |
| 24 |
|
| 25 |
Z3py Features |
| 26 |
|
| 27 |
This implementation contains no tuning. It was contributed by Mark Liffiton and it is |
| 28 |
a simplification of one of the versions available from his Marco Polo Web site. |
| 29 |
It illustrates the following features of Z3's Python-based API: |
| 30 |
1. Using assumptions to track unsatisfiable cores. |
| 31 |
2. Using multiple solvers and passing constraints between them. |
| 32 |
3. Calling the C-based API from Python. Not all API functions are supported over the |
| 33 |
Python wrappers. This example shows how to get a unique integer identifier of an AST, |
| 34 |
which can be used as a key in a hash-table. |
| 35 |
|
| 36 |
Idea of the Algorithm |
| 37 |
The main idea of the algorithm is to maintain two logical contexts and exchange information |
| 38 |
between them: |
| 39 |
|
| 40 |
1. The MapSolver is used to enumerate sets of clauses that are not already |
| 41 |
supersets of an existing unsatisfiable core and not already a subset of a maximal satisfying |
| 42 |
assignment. The MapSolver uses one unique atomic predicate per soft clause, so it enumerates |
| 43 |
sets of atomic predicates. For each minimal unsatisfiable core, say, represented by predicates |
| 44 |
p1, p2, p5, the MapSolver contains the clause !p1 | !p2 | !p5. For each maximal satisfiable |
| 45 |
subset, say, represented by predicats p2, p3, p5, the MapSolver contains a clause corresponding |
| 46 |
to the disjunction of all literals not in the maximal satisfiable subset, p1 | p4 | p6. |
| 47 |
2. The SubsetSolver contains a set of soft clauses (clauses with the unique indicator atom occurring negated). |
| 48 |
The MapSolver feeds it a set of clauses (the indicator atoms). Recall that these are not already a superset |
| 49 |
of an existing minimal unsatisfiable core, or a subset of a maximal satisfying assignment. If asserting |
| 50 |
these atoms makes the SubsetSolver context infeasible, then it finds a minimal unsatisfiable subset |
| 51 |
corresponding to these atoms. If asserting the atoms is consistent with the SubsetSolver, then it |
| 52 |
extends this set of atoms maximally to a satisfying set. |
| 53 |
""" |
| 54 |
|
| 55 |
from z3 import * |
| 56 |
|
| 57 |
def main(): |
| 58 |
x, y = Reals('x y') |
| 59 |
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)] |
| 60 |
csolver = SubsetSolver(constraints) |
| 61 |
msolver = MapSolver(n=csolver.n) |
| 62 |
for orig, lits in enumerate_sets(csolver, msolver): |
| 63 |
output = "%s %s" % (orig, lits) |
| 64 |
print(output) |
| 65 |
|
| 66 |
|
| 67 |
def get_id(x): |
| 68 |
return Z3_get_ast_id(x.ctx.ref(),x.as_ast()) |
| 69 |
|
| 70 |
|
| 71 |
class SubsetSolver: |
| 72 |
constraints = [] |
| 73 |
n = 0 |
| 74 |
s = Solver() |
| 75 |
varcache = {} |
| 76 |
idcache = {} |
| 77 |
|
| 78 |
def __init__(self, constraints): |
| 79 |
self.constraints = constraints |
| 80 |
self.n = len(constraints) |
| 81 |
for i in range(self.n): |
| 82 |
self.s.add(Implies(self.c_var(i), constraints[i])) |
| 83 |
|
| 84 |
def c_var(self, i): |
| 85 |
if i not in self.varcache: |
| 86 |
v = Bool(str(self.constraints[abs(i)])) |
| 87 |
self.idcache[get_id(v)] = abs(i) |
| 88 |
if i >= 0: |
| 89 |
self.varcache[i] = v |
| 90 |
else: |
| 91 |
self.varcache[i] = Not(v) |
| 92 |
return self.varcache[i] |
| 93 |
|
| 94 |
def check_subset(self, seed): |
| 95 |
assumptions = self.to_c_lits(seed) |
| 96 |
return (self.s.check(assumptions) == sat) |
| 97 |
|
| 98 |
def to_c_lits(self, seed): |
| 99 |
return [self.c_var(i) for i in seed] |
| 100 |
|
| 101 |
def complement(self, aset): |
| 102 |
return set(range(self.n)).difference(aset) |
| 103 |
|
| 104 |
def seed_from_core(self): |
| 105 |
core = self.s.unsat_core() |
| 106 |
return [self.idcache[get_id(x)] for x in core] |
| 107 |
|
| 108 |
def shrink(self, seed): |
| 109 |
current = set(seed) |
| 110 |
for i in seed: |
| 111 |
if i not in current: |
| 112 |
continue |
| 113 |
current.remove(i) |
| 114 |
if not self.check_subset(current): |
| 115 |
current = set(self.seed_from_core()) |
| 116 |
else: |
| 117 |
current.add(i) |
| 118 |
return current |
| 119 |
|
| 120 |
def grow(self, seed): |
| 121 |
current = seed |
| 122 |
for i in self.complement(current): |
| 123 |
current.append(i) |
| 124 |
if not self.check_subset(current): |
| 125 |
current.pop() |
| 126 |
return current |
| 127 |
|
| 128 |
|
| 129 |
|
| 130 |
class MapSolver: |
| 131 |
def __init__(self, n): |
| 132 |
"""Initialization. |
| 133 |
Args: |
| 134 |
n: The number of constraints to map. |
| 135 |
""" |
| 136 |
self.solver = Solver() |
| 137 |
self.n = n |
| 138 |
self.all_n = set(range(n)) # used in complement fairly frequently |
| 139 |
|
| 140 |
def next_seed(self): |
| 141 |
"""Get the seed from the current model, if there is one. |
| 142 |
Returns: |
| 143 |
A seed as an array of 0-based constraint indexes. |
| 144 |
""" |
| 145 |
if self.solver.check() == unsat: |
| 146 |
return None |
| 147 |
seed = self.all_n.copy() # default to all True for "high bias" |
| 148 |
model = self.solver.model() |
| 149 |
for x in model: |
| 150 |
if is_false(model[x]): |
| 151 |
seed.remove(int(x.name())) |
| 152 |
return list(seed) |
| 153 |
|
| 154 |
def complement(self, aset): |
| 155 |
"""Return the complement of a given set w.r.t. the set of mapped constraints.""" |
| 156 |
return self.all_n.difference(aset) |
| 157 |
|
| 158 |
def block_down(self, frompoint): |
| 159 |
"""Block down from a given set.""" |
| 160 |
comp = self.complement(frompoint) |
| 161 |
self.solver.add( Or( [Bool(str(i)) for i in comp] ) ) |
| 162 |
|
| 163 |
def block_up(self, frompoint): |
| 164 |
"""Block up from a given set.""" |
| 165 |
self.solver.add( Or( [Not(Bool(str(i))) for i in frompoint] ) ) |
| 166 |
|
| 167 |
|
| 168 |
|
| 169 |
def enumerate_sets(csolver, map): |
| 170 |
"""Basic MUS/MCS enumeration, as a simple example.""" |
| 171 |
while True: |
| 172 |
seed = map.next_seed() |
| 173 |
if seed is None: |
| 174 |
return |
| 175 |
if csolver.check_subset(seed): |
| 176 |
MSS = csolver.grow(seed) |
| 177 |
yield ("MSS", csolver.to_c_lits(MSS)) |
| 178 |
map.block_down(MSS) |
| 179 |
else: |
| 180 |
seed = csolver.seed_from_core() |
| 181 |
MUS = csolver.shrink(seed) |
| 182 |
yield ("MUS", csolver.to_c_lits(MUS)) |
| 183 |
map.block_up(MUS) |
| 184 |
|
| 185 |
main() |
| 186 |
|