Z3の対称性破壊 - UFBVロジックのコンテキスト（新しいバージョン）

StackOverflow https://stackoverflow.com/questions/9300754

  •  25-10-2019
  •  | 
  •  

質問

（これは私の助けを得ようとする私の2回目です。質問/アプローチが意味をなさないか、明確ではない場合は、私に知らせてください。私のSBAでZ3）

UFBV Z3ロジックを使用して、リレーショナル仕様の境界検証に取り組んでいます。私が調査している現在の問題は、すべての可能なモデルの改ざん（リーチ可能性の述語の否定的な使用のため）を必要とし、より高い境界でソルバーのパフォーマンスを殺します。

可能なモデルの一部のみが実際に興味深いものであるため（他の人には同型ではありません）、私は対称性破壊技術（SAT領域で知られている）を導入しようとしています。

ただし、私が対称性を破壊するものと呼ぶものを使用すると、場合によってはZ3のパフォーマンスが向上する可能性がありますが、ソルバーの一般的な動作は不安定になります。

私のアプローチの1つ（私は最も有望なものだと思います）は、関係の対称性を破ることに基づいて、彼らのドメインを書き込みます。関係Rの各ドメインdと各原子a in d axiomsを導入します。これは、r^{m}とr^{m [a+1/a]}のバイナリ表現に関する順序を強制します。仕様のモデル。均一な関係のために、公理は緩和されます。

re subset axa a relationになります。 Rのための私のリラックスした対称性壊れた公理は次のように見えます：

;; 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)))
))))

私の問題は、このSBAを使用する効果は安定していない/一貫性がないことです。バウンドとバウンドまで異なり、別の仕様に仕様を形成します。また、SBAのすべてまたは1つの使用の使用は、パフォーマンスに影響します。

SATコンテキストでは、いわゆる対称性破壊述語（SBP）の成功は、SATソルバーのバックトラッキング機能に基づいています。とりわけ、SBPS。

  • Z3のコンテキストの違い（もしあれば）は何ですか？
  • これらの公理を使用して検索スペースを剪定するためにSolveを強制するにはどうすればよいですか（バックトラックの場合）？
  • 私のSBAに（定量的）パターンの使用が役立ちますか？

よろしく、

Aboubakr Achraf el Ghazi

役に立ちましたか？

解決

Z3 3.2には、定量化された式を処理するための2つの主要なエンジンがあります：eマッチングとMBQI（モデルベースの定量装置インスタンス化）。 eマッチングは、満足できない式でのみ有効です。 Z3は、このエンジンを使用してフォーミュラが満足できることを示すことができません。 MBQIはより高価ですが、いくつかのクラスのフォーミュラ（量子を含む）が満足できることを示すことができます。 Z3ガイド これらの2つのエンジン（およびその他のオプション）について説明します。 Z3を非自明の問題に効果的に使用するには、これらの2つのエンジンがどのように機能するかを理解することは非常に便利です。

対称性の破壊は、通常、検索空間を減らすための非常に効果的な方法です。あなたの問題で何が起こっているのかを正確に特定するのは難しいです。非安定した動作については、次の説明を見ることができます。

  • MBQIは、SBAを満たすモデルを作成するのに苦労しています。 SBAは検索スペースを剪定しますが、問題が満たす可能性がある場合、Z3はそれらを満たす解釈（モデル）を構築しようとします。したがって、この場合、SBAはちょうど頭上です。入力式が非常に簡単に満足しているが、SBAを追加すると難しくなる場合、これは特に当てはまります。オプションを使用して、この仮説を確認できます MBQI_TRACE=true. 。 Z3は次のようなメッセージを表示します。 [mbqi] failed k!18. 。どこ k![line-number] 量子IDです。タグを使用して独自のIDを割り当てることができます :qid. 。これが例です：

    （assert（forall（（x t）（y t）））（！（=>（（and（subtype xy）（subtype yx））（= xy）：qid antimmetry）））））））

ところで、MBQIモジュールを使用して無効にすることができます MBQI=false.

Z3の将来のバージョンでは、いくつかの定量化された式に対してMBQIを無効にするオプションを追加することを計画しています。この機能は、SBAに役立つ場合があります。

  • 別の説明は、eマッチングがSBAの多くのインスタンスを作成していることです。オプションを使用することを確認できます QI_PROFILE=true. 。 Z3は次のような情報をダンプします：

Quantifier_Instances]反対称性：12：1：2.00

最初の数字は、生成されたインスタンスの数です。それが問題の原因である場合、1つの解決策は、あまりにも多くのインスタンスを生成しているSBAに制限パターンを割り当てることです。たとえば、Z3が使用します (R ai aj) のパターンとして SBA(R, A)_upToDiag. 。この種のパターンは、二次数のインスタンスを作成する可能性があります。別の実験は、eマッチングの無効化で構成されています。たとえば、オプション

AUTO_CONFIG=false EMATCHING=false MBQI=true

また、上記の構成で関連性の伝播を無効にしようとすることもできます。 RELEVANCY=0.

最後に、別のオプションは、有用であると思われるSBAのインスタンスを生成し、定量化された式を削除することです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top