Zählen der Anzahl der zufriedenen Modelle - gegeben mathematische Einschränkungen

Question

Frage

Es gibt viele Algorithmen zum Lösen der #sat Problem, mit einem Wesen Der DPLL-Algorithmus und ist für alle Arten von Programmiersprachen implementiert. Soweit ich gesehen habe, nehmen sie alle eine boolesche Formel auf CNF als Input und gibt die Anzahl der zufriedenen Interpretationen aus.

mathematische Einschränkungen dagegen ist eine andere Weise, eine Instanz zu definieren von SAT-Problem und wird häufig in der diskreten Optimierung verwendet, in der man versucht, einige Funktion in Bezug auf diese Einschränkungen zu optimieren. Gibt es ein Programm, das mathematische Einschränkungen als Input einnimmt und die Anzahl der zufriedenen Interpretationen ausgibt?

Beispiel

wir repräsentieren die boolesche Formel $ q= (a \ lor b) \ wedge (c \ lor d) $ als Einschränkungen als $$ A + B \ GEQ 1 \\ C + D \ GEQ 1 $$ oder als Matrix $ A $ und Support-Vektor < Span-Klasse="Math-Container"> $ B $ $$ A= \ begin {bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \ ende {bmatrix} \\ B=beginnen {bmatrix} 1 & 1 \ ter {bmatrix} $$

wo alle Variablen $ a, b, c, d \ in \ {0,1 \} $ . Wir wissen, dass es Programme gibt, die $ q $ als Input gibt und die Anzahl der Interpretationen ausgibt, gibt es jedoch Programme, die $ A $ < / span> und $ B $ als Eingabe (oder ähnlicher Konstruktion) und gibt die gleiche Anzahl von Interpretationen aus?

Answer 1

Ich kenne zwei vernünftige Ansätze.

Annäherung # 1 : Zählen Sie die Anzahl der ganzzahligen Punkte in einem konvexen Polytop.

Der Satz von linearen Ungleichheiten, den Sie mit den Ungleichungen $ 0 \ le a, b, c, d \ le 1 $ ein konvexes Polytop definieren. Jetzt möchten Sie Zählen Sie die Anzahl der ganzzahligen Punkte, die in dieses Polytop fallen. .

Es gibt Standard-Algorithmen dafür, dass Sie direkt anwenden können. Wenn Sie nach "Zählen von Integer-Punkte in Polytope" oder "Zählen von Gitterpunkten in Polytop" suchen, finden Sie viele Forschungspapiere. Sehen Sie, zB https://cstheory.steckexchange.com/Q/22280/5038 , Finding alle Lösungen für eine ganzzahlige lineare Programmierung (ILP) probleme .

Annäherung # 2 : in CNF konvertieren, und verwenden Sie einen #sat-Solver.

Sie können Ihre Einschränkungen immer in eine CNF-Formel konvertieren. Jede lineare Ungleichung kann in einen Satz von CNF-Klauseln umgewandelt werden. Eine lineare Ungleichheit des Formulars $ x_i + \ dots + x_j \ ge 1 $ entspricht unmittelbar mit der CNF-Klausel $ (x_i \ lor \ dots \ lor x_j) $ . Für eine allgemeinere lineare Ungleichheit des Formulars $ X_I + \ DOTS + X_J \ GE C $ möchten Sie die Einschränkung zumindest $ C $ aus der $ K $ variablen $ x_i, \ dots, x_j $ sind wahr. Es gibt viele Standardwende, um das zu kodieren. Siehe https://cstheory.steckexchange.com/q/23771/5038 , Das folgende Problem zum Sat , codieren 1 -On-of-n-Einschränkung für SAT-Löser ,

(ein Ansatz ist, einen booleschen Kreislauf zu konvertieren, der berechnet, $ x_i + \ dots + x_j $ und vergleicht sie mit $ C $ und konvertieren Sie dann den booleschen Kreislauf mit dem tseitin transform . Sie können einen solchen booleschen Kreislauf mit Standard-Addierer- und Komparatorschaltungen erstellen. Es gibt jedoch auch viele andere Wege.)

Wenn Sie einmal über eine CNF-Formel verfügen, die dem Satz von Einschränkungen entspricht, können Sie ein beliebiges AUS-THE-SHELF #sat-Solver verwenden, um die Anzahl der Lösungen für diese CNF-Formel zuzählen.

---

Es ist schwer zu sagen, welcher dieser beiden Ansätze besser funktionieren wird; Möglicherweise müssen Sie sie beide in den Fällen von Instanzen ausprobieren, mit denen Sie sich damit umsehen, um sicher zu wissen. Ich würde erwarten, dass, wenn Sie lineare Ungleichheiten des Formulars $ X_I + \ DOTS + X_J \ GE C $ wohnen $ C $ ist groß, dann kann der Ansatz Nr. 1 überlegen sein; Wenn jedoch $ C $ normalerweise klein ist, kann der Ansatz # 2 überlegen sein.

Answer 2

Sie können DPLL mit den Einschränkungen anstelle von Klauseln direkt implementieren.Dies erfordert das Ändern der Datenstruktur und des Ausbreitungsalgorithmus, aber es funktioniert trotzdem.

Sobald alle Variablen der Einschränkung mit Ausnahme einer eingestellt sind, kann eine Einheitsausbreitung auftreten.

Sobald alle Variablen der Einschränkung eingestellt sind, kann ein Konflikt auftreten.

Der Rest des Algorithmus bleibt gleich.

Eine Einschränkung über booleschen Variablen ist nur eine Sammlung verborgener CNF-Klauseln (möglicherweise exponentiell viele Klauseln, abhängig von der Einschränkung).

Answer 3

Die Frage war seit antwortete auf oder.Stackexchange für Mixed-Integer-Programmiersoftware mit Beispielen vorhandener Software und Skripts (cplex, Scip, ...).

Dies ist ähnlicher dem CDCL-Algorithmus als auf DPLL: Wenn eine neue Lösung gefunden wird, wird eine neue Einschränkung hinzugefügt, um ihn zu verbieten, und die Suche wird wieder aufgenommen, bis das Problem inpositioniert wird.