Skip to main content

Strategies

High-performance solvers, such as Z3, contain many tightly integrated, handcrafted heuristic combinations of algorithmic proof methods. While these heuristic combinations tend to be highly tuned for known classes of problems, they may easily perform very badly on new classes of problems. This issue is becoming increasingly pressing as solvers begin to gain the attention of practitioners in diverse areas of science and engineering. In many cases, changes to the solver heuristics can make a tremendous difference.

In this tutorial we show how to create custom strategies using the basic building blocks available in Z3. Z3Py and Z3 implement the ideas proposed in this article.

Introduction​

Z3 implements a methodology for orchestrating reasoning engines where "big" symbolic reasoning steps are represented as functions known as tactics, and tactics are composed using combinators known as tacticals. Tactics process sets of formulas called Goals.

When a tactic is applied to some goal G, four different outcomes are possible. The tactic succeeds in showing G to be satisfiable (i.e., feasible); succeeds in showing G to be unsatisfiable (i.e., infeasible); produces a sequence of subgoals; or fails. When reducing a goal G to a sequence of subgoals G1, ..., Gn, we face the problem of model conversion. A model converter construct a model for G using a model for some subgoal Gi.

In the following example, we create a goal g consisting of three formulas, and a tactic t composed of two built-in tactics: simplify and solve-eqs. The tactic simplify apply transformations equivalent to the ones found in the command simplify. The tactic solver-eqs eliminate variables using Gaussian elimination. Actually, solve-eqs is not restricted only to linear arithmetic. It can also eliminate arbitrary variables. Then, combinator Then applies simplify to the input goal and solve-eqs to each subgoal produced by simplify. In this example, only one subgoal is produced.

In the example above, variable x is eliminated, and is not present the resultant goal.

In Z3, we say a clause is any constraint of the form Or(f_1, ..., f_n). The tactic split-clause will select a clause Or(f_1, ..., f_n) in the input goal, and split it n subgoals. One for each subformula f_i.

Tactics​

Z3 comes equipped with many built-in tactics. The command describe_tactics() provides a short description of all built-in tactics.

Z3Py comes equipped with the following tactic combinators (aka tacticals):

Then(t, s)applies t to the input goal and s to every subgoal produced by t.
OrElse(t, s)first applies t to the given goal, if it fails then returns the result of s applied to the given goal.
Repeat(t)Keep applying the given tactic until no subgoal is modified by it.
Repeat(t, n)Keep applying the given tactic until no subgoal is modified by it, or the number of iterations is greater than n.
TryFor(t, ms)Apply tactic t to the input goal, if it does not return in ms millisenconds, it fails.
With(t, params)Apply the given tactic using the given parameters.

The following example demonstrate how to use these combinators.

In the tactic split_solver, the tactic solve-eqs discharges all but one goal. Note that, this tactic generates one goal: the empty goal which is trivially satisfiable (i.e., feasible)

The list of subgoals can be easily traversed using the Python for statement.

A tactic can be converted into a solver object using the method solver(). If the tactic produces the empty goal, then the associated solver returns sat. If the tactic produces a single goal containing False, then the solver returns unsat. Otherwise, it returns unknown.

In the example above, the tactic bv_solver implements a basic bit-vector solver using equation solving, bit-blasting, and a propositional SAT solver. Note that, the command Tactic is suppressed. All Z3Py combinators automatically invoke Tactic command if the argument is a string. Finally, the command solve_using is a variant of the solve command where the first argument specifies the solver to be used.

In the following example, we use the solver API directly instead of the command solve_using. We use the combinator With to configure our little solver. We also include the tactic aig which tries to compress Boolean formulas using And-Inverted Graphs.

The tactic smt wraps the main solver in Z3 as a tactic.

Now, we show how to implement a solver for integer arithmetic using SAT. The solver is complete only for problems where every variable has a lower and upper bound.

Combining tactics with solvers​

Tactics can be combined with solvers. For example, we can apply a tactic to a goal, produced a set of subgoals, then select one of the subgoals and solve it using a solver. The next example demonstrates how to do that, and how to use model converters to convert a model for a subgoal into a model for the original goal.

Using tactics to simplify benchmarks​

You can also use tactics to transform SMTLIB problems. Some simplifications eliminate variables so they will not appear in the simplified formulas.

Probes​

Probes (aka formula measures) are evaluated over goals. Boolean expressions over them can be built using relational operators and Boolean connectives. The tactic FailIf(cond) fails if the given goal does not satisfy the condition cond. Many numeric and Boolean measures are available in Z3Py. The command describe_probes() provides the list of all built-in probes.

In the following example, we build a simple tactic using FailIf. It also shows that a probe can be applied directly to a goal.

Z3Py also provides the combinator (tactical) If(p, t1, t2) which is a shorthand for:

OrElse(Then(FailIf(Not(p)), t1), t2)

The combinator When(p, t) is a shorthand for:

If(p, t, 'skip')

The tactic skip just returns the input goal. The following example demonstrates how to use the If combinator.