Übersicht über Transformationen im Zusammenhang mit der Verwendung von SAT-Lösern

13

Ich beginne, die Möglichkeit zu untersuchen, mich auf einen SAT-Löser zu verlassen, um ein Optimierungsproblem zu lösen, an dem ich interessiert bin, und suche derzeit nach einer Umfrage, die Beispiele für "clevere" Transformationen in Varianten von SAT (dh Transformationen, die resultieren) enthält in einem Problem von vernünftiger Größe, da ich nicht daran interessiert bin, Härteergebnisse zu beweisen, sondern das Problem tatsächlich zu lösen), ungefähr im Geiste dessen, was in der Umfrage über kubische Graphen von Greenlaw und Petreschi zu finden ist , wenn ein Vergleich möglich ist zwischen den beiden gemacht.

Ist mir eine solche Umfrage entgangen, weil sie nicht existiert oder weil ich sie einfach verpasst habe?

ds.algorithms reference-request sat optimization Anthony Labarre
quelle
Was genau meinen Sie mit "Varianten von SAT"?
Giorgio Camerani
k
4
Keine Sorge, das ist das richtige Wort, das hätte ich verstehen sollen. Aus rein praktischer Sicht denke ich jedoch nicht, dass es wichtig ist (was am wichtigsten ist, wie sparsam Ihre Kodierung ist). Können Sie weitere Details zu dem Optimierungsproblem angeben, das Sie lösen möchten? Ich interessiere mich sehr für praktische Anwendungen von SAT und für die technischen Aspekte der SAT-Lösung.
Giorgio Camerani
Es klingt ein bisschen verwirrend, dass Sie von einem Optimierungsproblem sprechen, gleichzeitig aber auch von SAT. In der Regel benötigen Sie zur Optimierung etwas Stärkeres, z. B. MAX-SAT. Vielleicht könnten Sie das klarstellen.
Mikolas
Diese Frage könnte etwas verwandt sein: cstheory.stackexchange.com/q/4314/4506
Mikolas

Antworten:

9

Ich bin mir nicht sicher, ob Sie danach suchen, aber hier ist einer: JM Silva, Praktische Anwendungen der Booleschen Zufriedenheit .

Mikolas
quelle
2
Ich konnte nicht über Ihren Link darauf zugreifen, hier ist noch einer . Auf den ersten Blick scheint das Papier recht interessant zu sein, aber es konzentriert sich mehr auf Anwendungen als auf das, was ich suche.
Anthony Labarre
@Anthony naja du hast gesagt, du interessierst dich für den praktischen Aspekt :-) Wie auch immer, die existierenden Mainstream-Löser unterscheiden nicht wirklich zwischen verschiedenen Arten von SAT. In der Vergangenheit wurde beispielsweise an der Ausnutzung von Binärklauseln gearbeitet. Die vorhandenen Löser verwenden jedoch nur DPLL + unit prop + clause learning. Einige der Präprozessoren nutzen die Struktur jedoch aus. Aber auch hier nicht wirklich vom Standpunkt der Komplexität. Einstufung.
Mikolas
8

Kapitel 2 des Handbuchs zur Zufriedenheit untersucht die Aspekte, die bei der Gestaltung dieser Transformationen zu berücksichtigen sind, sowie eine Liste von Referenzen, die meine Frage beantworten. Dies hat mir geholfen, einige Beispiele zu finden, die man sich ansehen kann, um sich mit diesen Transformationen vertraut zu machen:

Anthony Labarre
quelle