26
Vollständige SAT- Solver Vortrag im Rahmen des Seminars Automatic Problem Solving Lehrstuhl für Wissensverarbeitung, Prof. Dr. Torsten Schaub Universität Potsdam Ben Hildebrand, Mario Wegner

Vollständige SAT-Solver

  • Upload
    gaetan

  • View
    66

  • Download
    0

Embed Size (px)

DESCRIPTION

Vollständige SAT-Solver. Vortrag im Rahmen des Seminars Automatic Problem Solving Lehrstuhl für Wissensverarbeitung, Prof. Dr. Torsten Schaub Universität Potsdam Ben Hildebrand, Mario Wegner. Gliederung. Einleitung DPLL, Tableau, Effizienzsteigerungen Heuristiken BCP SAT-Solver: Grasp - PowerPoint PPT Presentation

Citation preview

Page 1: Vollständige SAT-Solver

Vollständige SAT-Solver

Vortrag im Rahmen des SeminarsAutomatic Problem Solving

Lehrstuhl für Wissensverarbeitung, Prof. Dr. Torsten SchaubUniversität Potsdam

Ben Hildebrand, Mario Wegner

Page 2: Vollständige SAT-Solver

Gliederung

1. Einleitung2. DPLL, Tableau, Effizienzsteigerungen3. Heuristiken4. BCP5. SAT-Solver:

GraspSatoChaffBerkMinsiege

Page 3: Vollständige SAT-Solver

Einleitung SAT-Problem: Bestimmung einer

Variablenbelegung v, so dass Formel f wahr Grundverfahren

DPLL Vollständig Lokale Suchalgorithmen Unvollständig

Vollständigkeit Existiert eine Lösung, wird diese auch gefunden Der Algorithmus terminiert nach endlicher

Laufzeit ohne Lösung, wenn Problem keine Lösung hat

Page 4: Vollständige SAT-Solver

DPLL-Grundlagewhile (true){

if (!decide()) // if no unassigned varsreturn(satisifiable);

while (!bcp()) {

if (!resolveConflict())return(not satisfiable);

}}

bool resolveConflict(){

d = most recent decision not ‘tried both ways’;if (d == NULL) // no such d was found

return false;flip the value of d;mark d as tried both ways;undo any invalidated implications;return true;

}

Page 5: Vollständige SAT-Solver

Tableau Nummerierung von Variablen und

Klauseln Jede Variable hat

Feld für aktuellen Wert Jeweils eine Liste für Regeln in denen es

positiv bzw. negativ vorkommt Jede Regel hat

Liste von Literalen Erfüllt-Feld Anzahl unbelegter Variablen

Page 6: Vollständige SAT-Solver

Tableau Unit-Propagation -> Literale kommen

auf Stack Hole letztes Literal vom Stack

Markiere mit der gewählten Wahrheitszuweisung Markiere jede Klause, in der es positiv vorkommt

als erfüllt Alle Klauseln, in denen es negativ vorkommt

Wenn Klausel nicht schon erfüllt -> Erniedrige Zähler der Klausel um 1

Wenn Zähler = 1 Lege das unbelegte Literal auf den Stack

Merke alle Änderungen, damit Backtracking möglich ist

Page 7: Vollständige SAT-Solver

Effizienzsteigerung Lookahead

Auswertung von Informationen über verbleibenden Suchraum

Entscheidungs-Heuristiken Konsistenzsicherungsmechanismen

Forward Checking Lookback

Auswertung des bereits durchsuchten Raumes Backjumping (intelligentes Backtracking) Clause Learning

Propagationsmechanismus Die meisten modernen SAT-Solver nutzen Mechanismen

aus allen Kategorien

Page 8: Vollständige SAT-Solver

Heuristiken Decision-Belegungen hängen von der Entscheidung ab,

welche Variable ausgesucht werden soll

Strategie bestimmt Variable und so den Suchbaum

schwer zu entscheiden, welche Strategie besser bzw. zu bevorzugen ist

Anzahl der Entscheidungen/Konflikte? bewirken nicht alle die gleiche Anzahl von BCP-Operationen

Nicht alle Entscheidungen haben den gleichen Rechenaufwand

Suche nach der schnellsten Strategie

Page 9: Vollständige SAT-Solver

RAND

Auswahl der nächsten Entscheidung zwischen unbelegten Variablen per Zufall

Page 10: Vollständige SAT-Solver

Formula simplification heuristics

Formel F1 ist dann simpler als Formel F2, wenn g(F1) > g(F2), wobei g eine eine exponentiell gewichtete Summe der Klausel-Größe für eine gegebene Formel berechnet

Variablen werden nach Stärke eine Formel zu vereinfachen sortiert und vorrangig ausgewählt

g(F|x) · g(F|¬x) soll maximiert werden

Page 11: Vollständige SAT-Solver

Literal count heuristics

Einstufung der Variablen anhand der Anzahl ihres Auftretens in unerfüllten Klauseln

Variable mit dem höchsten Auftreten wird dann ausgewählt

CP(v) = Anzahl des Auftretens von v in unerfüllter KlauselCN(v) = Anzahl des Auftretens von ¬v in unerfüllter Klausel

DLCS (dynamic largest combined sum) heuristic:wähle v so, dass CP(v) + CN(v) maximal

DLIS (dynamic largest individual sum) heuristic

wähle v so, dass CP(v) oder CN(v) maximal

Page 12: Vollständige SAT-Solver

Bohm‘s Heuristik

Wähle ein Literal v, für dass der Vektor mit den Komponenten

maximal ist. Dabei ist die Anzahle der ungelösten Klauseln der Länge i (verbleibende Literale), in denen v auftritt…α und β werden experimentell ausgewählt

Bevorzugt für Literale, die kleine Klauseln erfüllen, wenn sie auf true gesetzt werden die Größe von kleinen Klauseln weiter reduzieren, wenn sie

auf false gesetzt werden

max{ ( ), ( )} min{ ( ) ( )}i i i i iH h v h v h v h v

ih

Page 13: Vollständige SAT-Solver

MOM‘s Heuristik

(Maximales Auftreten in Klauseln minimaler Länge) Wähle Literal v, so dass

maximiert wird. f(v) ist dabei die Anzahl des Auftretens eines Literals v in den kleinsten ungelösten Klauseln und k ein tuning-Parameter.

Bevorzugt für Klauseln mit einem hohen Auftreten von v oder ¬v

Fokus ist auf den aktuell kleinsten Klauseln

2 ( ( ) ( )) ( ) ( )k f v f v f v f v

Page 14: Vollständige SAT-Solver

Jeroslaw-Wang-Heuristik

Für ein gegebenes Literal v sei

wobei c = unerfüllte Klausel, in der v auftritt

JW-OS (one-sided): wähle ein v, für das J(v) maximal ist setze v auf wahr

JW-TS (two-sided): wähle ein v, für das J(v) + J(¬v) maximal ist für J(v) ≥ J(¬v) setze v auf wahr, sonst auf falsch

| |( ) 2 c

c

J v

Page 15: Vollständige SAT-Solver

Boolean Constraint Propagation (BCP) Aufgabe:

Identifikation von unit-Klauseln nach einer Variablenbelegung Erzeugen einer Implikation

BCP - 90% der Laufzeit eines DLL-Solvers Wird häufig ausgeführt Arbeitet weit gefächert und nicht-sequentiell über Datenstruktur „anschauen“ einer Klausel ist sehr kostenaufwendig

Problem: Datenstruktur um vieles größer als L2-Cache Industrie-Formeln haben hunderttausende Klauseln und Millionen Literale Clause-learning lässt Formel wachsen Variablenbelegung wirkt sich auf viele Klauseln aus Nur ein winziger Teil der Formel im Cache

Große Cache-Miss-Rate bottleneck

Ziel: BCP optimieren

Page 16: Vollständige SAT-Solver

GRASP Basis: DPL-Prozedur Features

Entscheidungsebenen Nichtchronoligisches Backtracking Backjumping Kausalitätsketten Implikationsgraphen Clause Learning

Suchalgorithmus Decide()

Choice Point mit Heuristik Deduce()

BCP Success / Conflict

Diagnose() Clause Learning: Aus Konflikten werden neue Formeln gewonnen

Erase() Implementiert Backjumping

Page 17: Vollständige SAT-Solver

GRASP Choice-Heuristik

Verschiedene Heuristiken implementiert Standard:

Variable und Belegung, die die meisten Klauseln erfüllt, wird gewählt

Dadurch auch hohe Wahrscheinlichkeit, in der Propagation viel zu produzieren

Greedy

Page 18: Vollständige SAT-Solver

GRASP – Decision Levels, Implikationsgraphen

Page 19: Vollständige SAT-Solver

GRASP - Konfliktanalyse Struktur des Konflikts wird analysiert Clause Learning

Alle Variablenbelegungen, die ursächlich zum Konflikt geführt haben, können der Klausel-DB als Klausel hinzugefügt werden Conflict induced Clauses

Failure Driven Assertions Wird der Konflikt unter anderen durch die aktuelle

Belegung der Decision Variable ausgelöst, kann diese mit umgekehrtem Wert angenommen werden

Conflict-Directed Backtracking Wenn alle konfliktauslösenden Variablen auf einer

frühreren Entscheidungsebene als aktuell Backjump zur höchsten enthaltenen Ebene

Vorteil: Nutzlose Traversierung von Suchraum ohne Lösungen wird vermieden

Page 20: Vollständige SAT-Solver

GRASP - Konfliktanalyse Space Bounded Diagnosis

Problem bisher: Anzahl der Konfliktklauseln steigt mit der Anzahl der Backtracks im schlechtesten Fall exponentielles Klausel-DB-Wachstum

Lösung: Einteilung in grüne und rote Konfliktklauseln abhängig von Größenparameter k

Grün: normale Handhabung Rot: nur, solange erfüllt, unerfüllt, oder Unit. Sonst:

Löschung Unique Implication Points

Umfangreichere Konfliktanalyse stärkere implizierte Konfliktklauseln (weniger Literale)

Dominators

Page 21: Vollständige SAT-Solver

SATO Basiert auf DLL-Algorithmus Hauptmotivation war das Lösen von Latin Square Problemen

nutzt optimierten BCP THL BCP (tail to head literals BCP) Hier werden immer nur die Head- und Tail-Literale beobachtet

2 Techniken haben sehr zur Verbesserung von SATO beigetragen:

Kombination der Heuristiken formula simplification und literal count

Konfliktanalyse durch intelligentes „backjumping“

Page 22: Vollständige SAT-Solver

CHAFF arbeitet mit DP-Algorithmus scheduled lazy clause deletion Restart Konfliktanalyse, conflict clause addition und UIP-Identifikation

wie bei GRASP benutzt optimierten BCP TWL BCP (two watched literals BCP)

2 Literale einer Klausel werden beobachtet Solange nicht eines der beiden Literale auf 0 gesetzt

wird, wird die Klausel nicht besucht verwendet Variable State Independent Decaying Sum (VSIDS)

Heuristik Counter für Literale, welcher inkrementiert wird, wenn

eine Klausel zur Datenbank hinzugefügt wird, in der das Literal auftritt

Im Fall einer notwendigen Entscheidung wird das Literal mit dem höchsten Counter gewählt

Page 23: Vollständige SAT-Solver

BerkMin Nutzt die Entwicklungen von GRASP, CHAFF,

SATO Neuerungen

Organisation der gelernten Konfliktklauseln Zeitlich geordneter Stack Neueste (gelernte) Klauseln liegen ganz oben Grund: Neue Klauseln haben mehr Propagationspotenzial

als alte Andere Berechnung der Variablenaktivität

Aktivität = Anzahl Klauseln, die für Konflikte verantwortlich sind und in denen diese Variable vorkommt

Periodische Abwertung wie in Chaff, jedoch mit stärkerem Faktor

Page 24: Vollständige SAT-Solver

BerkMin Neuerungen

Choice – Heuristik 1. Basis: Chronologische Reihenfolge der

Konfliktklauseln Erste Konfliktklausel vom Stack: Variable mit

Max(Aktivität(Variable)) wird verwendet 2. Wenn keine Konfliktklauseln auf Stack:

Max(Aktivität(Variable)) Neues Klausel-DB-Management

Vor jeder Iteration Konflikt-Klauseln werden entfernt

Unwichtige (gemessen an ihrer Aktivität) Zu große

Datenstrukturen werden physisch zusammengeschoben

Page 25: Vollständige SAT-Solver

siege basiert auf DLL Verwendete Heuristik:

VMFT (variable move-to-front decision) heuristic Counter für Variablen + Variablenliste Score-Schema kann durch VSIDS ergänzt

werden Binary und ternary clause BCP (Erweiterung von TWL

BCP)

Page 26: Vollständige SAT-Solver

Referenzen [LA97] C. Li and Anbulagan. Heuristics based on unit propagation for satisability

problems. In Proceedings of the 15th International Joint Conference on Articial Intelligence (IJCAI'97), pages 366-371, 1997.

[BS96] R. Bayardo and R. Schrag. Using csp look-back techniques to solve exceptionally hard sat instances. In Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP'96), pages 46-60, 1996.

[MSS99] J. Marques-Silva and K. Sakallah. Grasp: A search algorithm for propositional satisability. IEEE Transactions on Computers, 48(5):506-521, 1999.

[Zha97] H. Zhang. Sato: an ecient propositional prover. In Proceedings of the 14th International Conference on Automated Deduction (CADE'97), pages 272-275, 1997.

[MMZ+01] M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, and S. Malik. Cha: Engineering an ecient sat solver. In Proceedings of the 38th Conference on Design Automation (DAC'01), pages 530-535, 2001.

[GN02] E. Goldberg and Y. Novikov. Berkmin: A fast and robust sat solver. In Proceedings of the 5th Conference on Design, Automation and Test in Europe (DATE'02), pages 142-149, 2002.

[Rya04] L. Ryan. Ecient algorithms for clause-learning sat solvers. Master's thesis, Simon Fraser University, 2004.