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

25

Ich verwende einen SAT-Löser, um ein Problem zu kodieren, und als Teil der SAT-Instanz habe ich boolesche Variablen x1,x2,,xn 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 x1,,xn 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 1x 2x n , um sicherzustellen , dass mindestens ein wahr ist.¬xi¬xji,jxix1x2xn

    Dies fügt -Klauseln und keine zusätzlichen booleschen Variablen hinzu.Θ(n2)

  • 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 = j istlgni1,i2,,ilgni1inixixjj .i=jxj

    Dies fügt -Klauseln hinzu und ich weiß nicht, wie viele zusätzliche boolesche Variablen es gibt.Θ(nlgn)

  • 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).x1+x2++xn=1xi

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

    Ein Spezialfall dieses Ansatzes ist Booleschen Variablen einzuführen , mit der Idee , dass y i den Wert enthalten sollte , x 1x 2x i . Diese Absicht kann durch Hinzufügen der Klauseln durchgesetzt werden y i¬ x i , y i¬ y i - 1 , und ¬ y ix iy i -y1,,ynyix1x2xiyi¬xiyi¬yi1 (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.¬yixiyi1y0i=1,,n¬yi¬xi+1i=1,2,,n1

  • 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 2x 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.nn00001nx1x2xn

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

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.knk=1

DW
quelle
Die meisten modernen SAT-Solver unterstützen standardmäßig Kardinalitätsklauseln und andere spezielle (Nicht-CNF-) Einschränkungen.
Dávid Horváth

Antworten:

12

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.

Kyle Jones
quelle
2
Wenn "kleine Gruppe" die Größe zwei hat, dann ist dies nur eine binäre Addition, wobei "Kommandant" das Ergebnisbit ist und der Übertrag als falsch bestätigt wird. Diese Methode ist vollständig allgemein gehalten (funktioniert für 1 von N) und praktisch durchführbar.
d8d0d65b3f7cf42
3

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 1x n ) . Wir können auch erzwingen, dass die beiden Kodierungen mit 2 lg n übereinstimmennx1,,xny1,,ybb=lgn(x1xn)2lgnKlauseln: Wir addieren einfach oder x ixi¬yj , 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.xiyjji

knx1,,xny1,,ynykyk+1O(nlg2n)O(nlg2n)

Das Papier ist

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

nkn

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

DW
quelle