Codierung der 1-aus-n-Bedingung für SAT-Löser

Ich verwende einen SAT-Löser, um ein Problem zu kodieren, und als Teil der SAT-Instanz habe ich boolesche Variablen $x_1,x_2,\dots,x_n$ wobei genau eine davon wahr sein soll und der Rest wahr sein soll falsch sein. (Ich habe dies manchmal als "One-Hot" -Codierung beschrieben gesehen.)

Ich möchte die Bedingung "genau eine von $x_1,\dots,x_n$ muss wahr sein" in SAT codieren . Wie kann diese Einschränkung am besten codiert werden, damit der SAT-Solver so effizient wie möglich ausgeführt wird?

Ich sehe viele Möglichkeiten, diese Einschränkung zu kodieren:

• Paarweise Einschränkungen. Ich konnte paarweise hinzufügen , Constraints für alle i , j , um sicherzustellen , dass höchstens ein x i wahr ist, und fügen Sie dann x 1 ∨ x 2 ∨ ⋯ ∨ x n , um sicherzustellen , dass mindestens ein wahr ist.$\neg x_i \lor \neg x_j$$i,j$$x_i$$x_1 \lor x_2 \lor \cdots \lor x_n$

  Dies fügt -Klauseln und keine zusätzlichen booleschen Variablen hinzu.$\Theta(n^2)$

• Binäre Codierung. Ich könnte neue boolesche Variablen i 1 , i 2 , ... , i lg n einführen , um (in binärer Form) eine ganze Zahl i so darzustellen, dass 1 ≤ i ≤ n (Hinzufügen einiger boolescher Bedingungen, um sicherzustellen, dass i im gewünschten Bereich liegt) ). Dann kann ich Einschränkungen hinzufügen, die erzwingen, dass x i ein Baum ist und dass alle anderen x j falsch sind. Mit anderen Worten, für jedes j fügen wir Klauseln hinzu, die erzwingen, dass i = $\lg n$$i_1,i_2,\dots,i_{\lg n}$$i$$1 \le i \le n$$i$$x_i$$x_j$$j$ .$i=j \Leftrightarrow x_j$

  Dies fügt -Klauseln hinzu und ich weiß nicht, wie viele zusätzliche boolesche Variablen es gibt.$\Theta(n \lg n)$

• Zählen Sie die Anzahl der wahren Werte. Ich könnte einen Baum von Booleschen Addierschaltungen implementieren und fordern und jedes x i als 0 oder 1 anstelle von falsch oder wahr behandeln und die Tseitin-Transformation verwenden, um die Schaltung in SAT umzuwandeln Klauseln. Ein Baum von Halbaddierern reicht aus: Beschränken Sie die Übertragausgabe jedes Halbaddierers auf 0, und beschränken Sie die Endausgabe des letzten Halbaddierers im Baum auf 1. Der Baum kann beliebig geformt sein ( ausgeglichener binärer Baum oder unsymmetrisch oder was auch immer).$x_1+x_2+\dots+x_n=1$$x_i$

  Dies kann in Gattern geschehen und fügt somit Θ ( n ) Klauseln und Θ ( n ) neue boolesche Variablen hinzu.$\Theta(n)$$\Theta(n)$$\Theta(n)$

  Ein Spezialfall dieses Ansatzes ist Booleschen Variablen einzuführen , mit der Idee , dass y i den Wert enthalten sollte , x 1 ∨ x 2 ∨ ⋯ ∨ x i . Diese Absicht kann durch Hinzufügen der Klauseln durchgesetzt werden y i ∨ ¬ x i , y i ∨ ¬ y i - 1 , und ¬ y i ∨ x i ∨ y i $y_1,\dots,y_n$$y_i$$x_1 \lor x_2 \lor \cdots \lor x_i$$y_i \lor \neg x_i$$y_i \lor \neg y_{i-1}$ (wobei wir y 0 als Synonym für falsch behandeln) füri=1,…,n. Als nächstes können wir die Restriktionen¬ y i ∨¬ x i + 1 füri=1,2,…,n-1addieren. Dies entspricht im Wesentlichen der Tseitin-Transformation eines Halbaddiererbaums, bei der der Baum eine maximal unausgeglichene Form aufweist.$\neg y_i \lor x_i \lor y_{i-1}$$y_0$$i=1,\dots,n$$\neg y_i \lor \neg x_{i+1}$$i=1,2,\dots,n-1$

• Schmetterlingsnetzwerk. Ich könnte ein Schmetterlingsnetz auf Bits aufbauen , den n- Bit-Eingang auf 000 ⋯ 01 beschränken, den n- Bit-Ausgang auf x 1 x 2 ⋯ x n beschränken und jedes 2-Bit-Schmetterlingsgatter als unabhängiges Gatter behandeln das tauscht entweder seine Eingabe mit der Entscheidung, was zu tun ist, basierend auf einer frischen neuen booleschen Variablen, die uneingeschränkt bleibt, aus oder tauscht sie nicht aus. Dann kann ich die Tseitin-Transformation anwenden, um die Schaltung in SAT-Klauseln umzuwandeln.$n$$n$$000\cdots 01$$n$$x_1 x_2 \cdots x_n$

  Dies erfordert Gatter und fügt somit Θ ( n lg n ) Klauseln und Θ ( n lg n ) neue boolesche Variablen hinzu.$\Theta(n \lg n)$$\Theta(n \lg n)$$\Theta(n \lg n)$

Gibt es andere Methoden, die ich übersehen habe? Welches soll ich verwenden? Hat jemand dies getestet oder sie experimentell ausprobiert oder hat jemand irgendwelche Erfahrungen mit diesen? Ist die Anzahl der Klauseln und / oder die Anzahl der neuen booleschen Variablen eine gute Ersatzmetrik für die Abschätzung der Auswirkungen auf die Leistung des SAT-Lösers, oder wenn nicht, welche Metrik würden Sie verwenden?

Ich habe gerade bemerkt, dass diese Antwort einige Hinweise zur Durchsetzung von Kardinalitätsbeschränkungen für SAT enthält, dh zur Durchsetzung der Beschränkung, dass genau aus den n Variablen wahr sind. Meine Frage ist also ein Sonderfall mit k = 1 . Vielleicht hilft die Literatur über Kardinalitätsbeschränkungen, meine Frage zu beleuchten.$k$$n$$k=1$

Für den Spezialfall von k aus n Variablen true mit k = 1 gibt es eine Befehlsvariablencodierung, wie in Effiziente CNF-Codierung zur Auswahl von 1 bis N Objekten von Klieber und Kwon beschrieben. Vereinfacht: Unterteilen Sie die Variablen in kleine Gruppen und fügen Sie Klauseln hinzu, die den Status einer Befehlsvariablen darauf hinweisen, dass eine Gruppe von Variablen entweder alle falsch oder alle bis auf einen falsch ist. Wenden Sie dann rekursiv denselben Algorithmus auf die Befehlsvariablen an. Fordern Sie am Ende des Prozesses, dass genau eine der wenigen Variablen für den endgültigen Befehlshaber wahr ist. Das Ergebnis sind O (n) neue Klauseln und O (n) neue Variablen.

Angesichts der Allgegenwart von zwei beobachteten Literalen in DPLL-basierten Solvern halte ich das Wachstum der O (n) -Klausel für einen entscheidenden Vorteil gegenüber Kodierungsschemata, die mehr Klauseln hinzufügen würden.

Ein Artikel von Magnus Björk beschreibt zwei Techniken, die es wert sein könnten, ausprobiert zu werden.

Für 1-aus- kann man sowohl One-Hot- als auch Binärcodierung gleichzeitig verwenden. Wir haben also x 1 , ... , x n als One-Hot-Codierung und y 1 , ... , y b als Binärcodierung, wobei b = lg n . Wir können die "mindestens eine" Bedingung einfach in einer einzigen Klausel kodieren: ( x 1 ∨ ⋯ ∨ x n ) . Wir können auch erzwingen, dass die beiden Kodierungen mit 2 lg n übereinstimmen$n$$x_1,\dots,x_n$$y_1,\dots,y_b$$b = \lg n$$(x_1 \lor \dots \lor x_n)$$2 \lg n$Klauseln: Wir addieren einfach oder x $x_i \implies \neg y_j$ , je nachdem, ob das j- te Bit der binären Codierung von i 0 oder 1 ist. Schließlich folgt automatisch die Bedingung "höchstens eins". Auf diese Weise kann auch der Rest der SAT-Instanz die am besten geeignete Codierung verwenden.$x_i \implies y_j$$j$$i$

$k$$n$$x_1,\dots,x_n$$y_1,\dots,y_n$$y_k$$y_{k+1}$$O(n \lg^2 n)$$O(n \lg^2 n)$

Das Papier ist

Magnus Björk. Erfolgreiche SAT-Codierungstechniken . 25. Juli 2009.

$n$$k$$n$

Alan M. Frisch, Paul A. Giannaros. SAT-Kodierungen der At-Most-k-Bedingung: Einige alte, andere neue, andere schnelle, andere langsame . ModRef 2010.