Debian Codegraph @

examples/python/mus/marco.py

raw
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