Approximationsalgorithmen für MAXSAT

Der Versuch, die optimale Lösung für WEIGHTED-MAX-3SAT, die gewichtete Version des 3-SAT-Optimierungsproblems, zu finden, ist NP-schwer. Tatsächlich ist es nach dem PCP-Theorem nachweislich NP-schwer, die nicht gewichtete Version von MAX-SAT willkürlich gut zu approximieren.

Ein kanonischer Algorithmus zur Approximation von WEIGHTED-MAX-3SAT ist MAX-WalkSAT. Als ich mich umsah, fand ich einige Informationen zu anderen Algorithmen (z. B. Branch-and-Bound, DPL-Algorithmus), die häufig verwendet werden, um Lösungen für 3-SAT oder (ungewichtetes) MAX-3SAT zu finden, aber ich sah keine Diskussion darüber, wie Nun, diese würden für die gewichtete Version funktionieren. Intuitiv würden sie ohne Anpassung nicht so gut funktionieren.

Ich frage mich, welche anderen Algorithmen üblicherweise verwendet werden, um WEIGHTED-MAX-SAT zu approximieren, wenn es bekannte WEIGHTED-MAX-SAT-Löser gibt, und welche relative Qualität diese Algorithmen / Löser haben.

ds.algorithms approximation-algorithms sat approximation-hardness Huck Bennett
quelle

Dies ist nicht wirklich ein Thema, da es eher um Heuristik und Implementierungserfahrung als um nachweisbare Algorithmen geht.

Warren Schudy

@ Warren: Ich denke, das geht vielleicht etwas zu weit. Die Frage lautet im Wesentlichen: "Welche Algorithmen sind für WEIGHTED-MAX-SAT gut?" Das ist eine durchaus vernünftige Frage. Viele SAT-Löser verlassen sich auch auf Heuristiken. Obwohl ihre Worst-Case-Leistung schlecht ist, schneiden sie überraschend gut ab. Wenn sich jede Frage nur auf genau nachgewiesene Komplexitätsergebnisse bezieht, bezweifle ich, dass die Website sehr beliebt wäre. Immerhin haben wir schon den Zoo.

Joe Fitzsimons

Der MAXSAT-Wettbewerb hat Abteilungen für gewichtet und für ungewichtet: maxsat.udl.cat/10/results

Radu GRIGore

Hier ist eine lesbare Beschreibung eines der verwendeten Algorithmen: Scholar.google.com/scholar?cluster=14077294269217865108

Radu GRIGore

@Warren: In den 80er und 90er Jahren war die theoretische Informatik an vielen Universitäten sehr unbeliebt und wurde vom Rest der Informatik herabgesehen, weil sie als nicht mit der Praxis verbunden angesehen wurde. Schließlich haben Google und andere Erfolge sie davon überzeugt, dass es sich lohnt, mit uns zu sprechen. Lassen Sie uns jetzt bitte die Kommunikationswege von der anderen Seite nicht schließen, nachdem wir so lange daran gearbeitet haben, sie zu öffnen. Das wäre sehr schlecht für das Feld, ganz zu schweigen vom TCS-Arbeitsmarkt.

Peter Shor

Antworten:

Nun, dies kann als das Problem formuliert werden, den Grundzustand eines Ising-ähnlichen Hamiltonianers mit 3-lokalen Begriffen zu finden. Diese treten nicht auf natürliche Weise auf, aber Sie würden erwarten, dass sie sich ähnlich wie andere Systeme abkühlen. Daher sollte simuliertes Tempern für die gewichtete Version einwandfrei funktionieren.

Joe Fitzsimons
quelle

Joe, nachdem ich darüber nachgedacht habe, kann ich nicht sehen, wie sich simuliertes Tempern von MAX-WalkSAT unterscheidet. Ist MAX-WalkSAT nicht nur eine Form des simulierten Glühens, das auf dieses spezielle Problem angewendet wird?

Huck Bennett

@ Huck: Es hängt davon ab, wie Sie auswählen, welche Variablen umgedreht werden sollen.

Joe Fitzsimons

Ich denke, man kann eine Reduzierung durchführen, indem man einfach die Formeln entsprechend ihrem Gewicht dupliziert. Daher gelten die Ergebnisse der oberen und unteren Grenze für ungewichtetes 3-SAT auch für gewichtete Versionen mit willkürlich geringem Verlust. Und nach einem klassischen Ergebnis von Johan Håstad ist es NP-schwer, 3-SAT über 7/8 hinaus zu approximieren, was die Leistung der Zuweisung von Zufallswerten ist.

Ich bin mir nicht sicher über die Leistung der in der Praxis verwendeten Algorithmen.

Sangxia
quelle

Diese Reduktion ist in der Länge des Gewichts nicht polynomisch. Wenn Sie mir ein Gewicht der Länge O (n) geben, muss ich 2 ^ (O (n)) Kopien der Klausel anfertigen.

Huck Bennett

Wenn ich das Problem auf MAX-SAT mit nicht wiederholten Klauseln (immer noch NP-hart) beschränken würde, würde das nicht funktionieren.

Huck Bennett

Sicherlich gelten alle Untergrenzen (Härteergebnisse) für ungewichtetes 3-SAT auch für gewichtetes 3-SAT (das ungewichtetes 3-SAT subsumiert).

Neal Young