SAT-Löser lösen immer effizienter große Instanzen und werden in verschiedenen Zusammenhängen als Back-End eingesetzt. Jedes Mal, wenn jemand sie zur Lösung eines Problems in einem bestimmten Bereich verwenden möchte, muss er / sie eine Ad-hoc-Codierung entwickeln, die nicht nur die richtigen Lösungen bietet, sondern auch die Einschränkungen (auch überflüssig) in eine Form bringt Das hilft den Heuristiken der Löser dabei, eine Lösung schneller zu finden.
Viele solcher Kodierungen scheinen mir sehr verbreitet zu sein, zum Beispiel: Es wird behauptet, dass eine endliche Menge von Knoten als Baum oder als DAG verknüpft ist oder eine Liste sortiert ist ...
Gibt es ein Repository / Rezeptbuch mit allgemeinen Kodierungen für allgemeine Probleme mit optimierten Lösungen?
quelle
Antworten:
Ich habe vor einigen Jahren eine Umfrage gelesen, die relevant zu sein scheint: " Successful SAT Encoding Techniques " von Magnus Björk.
Abstrakt:
quelle
Es ist immer eine gute Idee, zuerst das Handbuch der Zufriedenheit [1] zu lesen (ich denke, es ist nicht frei verfügbar, sorry). Hier trägt Kapitel 2 den Titel "CNF-Codierungen". Zumindest bietet das Buch Literaturhinweise zum Stand der Technik zum Zeitpunkt des Schreibens, und Sie können Ihre Suche durch sie erweitern.
Darüber hinaus finden Sie hier und hier zwei aktuelle Folien zur SAT-Vorverarbeitung. Die Folien geben einen kurzen Überblick über die Vorverarbeitungstechniken sowie weitere Referenzen. Die Idee ist, anstatt zu versuchen, das Problem auf effiziente Weise "manuell" zu modellieren, es einfach auf die einfachste Weise zu modellieren.
[1] Biere, Armin, Marijn Heule und Hans van Maaren, Hrsg. Handbuch der Erfüllbarkeit. Vol. 185. IOS Press, 2009.
quelle
Dies ist keine direkte Antwort, sondern ein immer enger verwandterer Aspekt: Ein Teil davon wird durch ein relativ neues Forschungsgebiet abgedeckt, das als SMT, Satisfiability Modulo Theories, bekannt ist . Die Grundidee besteht darin, Problemkodierungen (z. B. Ganzzahlarithmetik, Diagramme usw.) in den SAT-Löser zu integrieren, aber auch das zusätzliche Wissen, das aus dieser Kopplung resultiert, zu nutzen, um fortschrittlichere Lösungsalgorithmen zu erstellen. Hier ist eine Umfrage. Wie bereits erwähnt, können sie wesentlich effizienter sein als die Kombination eines Ad-hoc-Codierungsmechanismus mit Standard-SAT-Lösern.
Satisfiability Modulo Theories: Ein Appetizer / Leonardo de Moura und Nikolaj Bjørner
quelle