Mehrfachzeitverkürzung von ILP zu SAT?

14

Wie bekannt ist, ist das 0-1-Entscheidungsproblem von ILP NP-vollständig. Es ist einfach zu zeigen, dass es sich um NP handelt, und die ursprüngliche Reduzierung stammte von SAT. Seitdem wurde gezeigt, dass viele andere NP-Complete-Probleme ILP-Formulierungen aufweisen (die als Reduktion von diesen Problemen auf ILP fungieren), da ILP sehr allgemein ist.

Reduzierungen von ILP scheinen viel schwieriger zu sein, entweder ich selbst oder um sie aufzuspüren.

Meine Frage ist daher, ob jemand eine Mehrfachzeitverkürzung von ILP zu SAT kennt, dh wie man ein 0-1 ILP-Entscheidungsproblem mit SAT löst.

codetaku
quelle

Antworten:

12

0-1 ILP formuliert als:

Gibt es einen Vektor , der Einschränkungen unterliegt:x

a11x1+a12x2...+a1nxnb1a21x1+a22x2...+a2nxnb2...am1x1+am2x2...+amnxnbm

xjxxj{0,1}

Reduktion auf k-sat:

Zuerst reduzieren, um saß Stromkreis:

ein1jxjb1

b1

ein1jb1

xj

Der endgültige CNF enthält alle Einschränkungen.

Realz Slaw
quelle
Ah, ich verstehe jetzt ... Ich habe irgendwie vergessen, die Möglichkeit, die Schaltung zu durchlaufen, zu nutzen ... Vielen Dank für Ihre Hilfe.
Codetaku
0

Es ist eine Art Nekro-Antwort auf eine bereits beantwortete und akzeptierte Frage, aber ich möchte darauf hinweisen, dass es einen wirklich einfacheren Weg gibt.

Angenommen, Sie haben eine der folgenden Ungleichungen:

5x1+2x2+3x36

(1,1,1)(1,1,0)(1,0,1)

(1,1,1)¬(x1x2x3)(¬x1¬x2¬x3)

(¬x1¬x2¬x3)(¬x1¬x2x3)(¬x1x2¬x3)

Durchqueren aller Ungleichungen und Sammeln von Klauseln erhalten Sie am Ende cnf. Oft ist diese CNF WEGE EINFACHER, dann eine, die sich aus einer akzeptierten Antwort ergibt. Die Kosten für die Vorverarbeitung sind jedoch höher.

Konstantin Vladimirov
quelle