Brisure de symétrie pour Z3 - dans le cadre de la logique UFBV (nouvelle version)

Question

(Ceci est mon deuxième essai pour obtenir de l'aide. Si la question / approche ne font pas de sens ou pas clair, s'il vous plaît me faire savoir. Je serais aussi heureux de toute petite indication ou référence, qui peut me aider à comprendre le comportement de Z3 avec mes SBAS)

Je travaille sur la vérification de la spécification relationnelle limitée en utilisant la logique UFBV Z3. Le problème actuel j'étudie, a besoin de la falsification de tous les modèles possibles (à cause d'une utilisation négative d'un prédicat de joignabilité), qui tue les performances du solveur dans les limites supérieures.

Du fait qu'une partie des modèles possibles sont en effet intéressant (pas isomorphes à d'autres), je suis en train d'introduire des techniques brisure de symétrie (connue dans la zone SAT).

Cependant, l'utilisation de ce que j'appelle axiomes rupture de symétrie peut améliorer les performances de Z3 dans certains cas, mais le général, le comportement du solveur devient instable.

L'une de mes approches (je pense que le plus prometteur), les bases sur briser la symétrie sur les relations w.r.t. leurs domaines. Il présente de chaque domaine D d'une relation R et chaque atome a \ in axiomes D, appliquer une commande sur la représentation binaire de R ^ {M} et R ^ {M [a + 1 / a]}, où M est un modèle pour la description. Pour les relations homogènes axiomes sont assouplies.

Laisse R \ subset axa une relation. Ma symétrie détendue rupture axiomes pour un look R comme ceci:

;; SBA(R, A)_upToDiag
(assert
 (forall ( (ai A) (aj A) )
  (=>
   (bvult ai aj)
   (=>
    (forall ((x A))
     (=>
       (bvult x aj)
       (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
     )
    )
    (=>
     (R ai aj)
     (R (bvadd  ai  (_ bv1 n)) aj)
)))))    

;; SBA(R, A)_diag
(assert
 (forall ( (ai A) )
  (=>
   (forall ((x A))
    (=>
      (bvult x ai)
      (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
    )
   )
   (=>
    (R ai ai)
    (R (bvadd  ai  (_ bv1 n)) (bvadd  ai  (_ bv1 n)))
)))) 

Mon problème est que l'effet d'utiliser cette SBAs n'est pas stable / cohérente. Elle diffère de la tenue de la spécification et la forme liée à une autre. En outre l'utilisation de tout ou seulement l'un des SBAs affecte les performances.

Dans le contexte SAT le succès de la soi-disant prédicat de rupture de symétrie (SBP) Les bases d'approche sur la capacité de retours en arrière du solveur SAT, qui (en quelque sorte) garantie que si la piste arrière du solveur, il sera alors élaguer la recherche l'espace en utilisant, entre autres, les SBP.

• Quelle est la différence (le cas échéant) dans le cadre de Z3?
• Comment puis-je appliquer Solve d'utiliser ces axiomes pour élaguer l'espace de recherche (quand il le suivi de retour)?
• Est-ce que l'utilisation de motifs (quantificateurs) pour mon aide SBAs?

Cordialement,

Aboubakr El Ghazi Achraf

Answer 1

In Z3 3.2, there are two main engines for handling quantified formulas: E-matching and MBQI (model based quantifier instantiation). E-matching is only effective in unsatisfiable formulas. Z3 will not be able to show that a formula is satisfiable using this engine. MBQI is more expensive, but it can show that several classes of formulas (containing quantifiers) are satisfiable. The Z3 guide describes these two engines (and other options). To use Z3 effectively on nontrivial problems, it is very useful to understand how these two engines work.

Symmetry breaking is usually very effective way to reduce the search space. It is hard to pinpoint exactly what is going on in your problem. I can see the following explanations for the non stable behavior:

• MBQI is having a hard time creating a model that satisfies the SBAs. Although the SBAs prune the search space, if the problem is satisfiable, Z3 will try to build an interpretation (model) that satisfies them. So, in this case, the SBA is just overhead. This is particularly true, if the input formula is very easy to satisfy, but becomes hard when you add the SBAs. You can confirm this hypothesis by using the option MBQI_TRACE=true. Z3 will display messages such as: [mbqi] failed k!18. Where k![line-number] is the quantifier id. You can assign your own ids using the tag :qid. Here is an example:

  (assert (forall ((x T) (y T)) (! (=> (and (subtype x y) (subtype y x)) (= x y)) :qid antisymmetry)))

BTW, you can disable the MBQI module using MBQI=false.

In future versions of Z3, we are planning to add an option to disable MBQI for some quantified formulas. This feature may be useful for SBAs.

• Another explanation is that E-matching is creating too many instances of the SBAs. You can confirm that using the option QI_PROFILE=true. Z3 will dump information such as:

[quantifier_instances] antisymmetry : 12 : 1 : 2.00

The first number is the number of generated instances. If that is the source of the problem, one solution is to assign restrictive patterns for the SBAs that are generating too many instances. For example, Z3 will use (R ai aj) as a pattern for SBA(R, A)_upToDiag. This kind of pattern may create a quadratic number of instances. Another experiment consists in disabling E-matching. Example, the option

AUTO_CONFIG=false EMATCHING=false MBQI=true

You may also try to disable relevancy propagation in the configuration above, option: RELEVANCY=0.

Finally, another option is to generate the instances of the SBAs that you believe are useful, and remove the quantified formulas.