Express-Boolesche Logikoperationen in der ganzzahligen linearen Programmierung (ILP)

58

Ich habe ein ganzzahliges lineares Programm (ILP) mit einigen Variablen , die Boolesche Werte darstellen sollen. Die müssen ganze Zahlen sein und entweder 0 oder 1 enthalten ( ).x i 0 x i1xixi0xi1

Ich möchte boolesche Operationen mit diesen 0/1-Variablen unter Verwendung linearer Bedingungen ausdrücken. Wie kann ich das machen?

Genauer gesagt möchte ich (Boolesches UND), (Boolesches ODER) und (Boolesches NICHT) . Ich verwende die offensichtliche Interpretation von 0/1 als Boolesche Werte: 0 = falsch, 1 = wahr. Wie schreibe ich ILP-Einschränkungen, um sicherzustellen, dass die wie gewünscht mit den Beziehung stehen ?y 2 = x 1x 2 y 3 = ¬ x 1 y i x iy1=x1x2y2=x1x2y3=¬x1yixi

(Dies könnte als Aufforderung zur Reduzierung von CircuitSAT auf ILP oder als Aufforderung zur Angabe eines Ausdrucks für SAT als ILP angesehen werden. Hier möchte ich jedoch eine explizite Möglichkeit zum Codieren der oben gezeigten logischen Operationen sehen.)

DW
quelle

Antworten:

66

Logisches UND: Verwenden Sie die linearen Bedingungen , , , , wobei eine ganze Zahl sein muss. Dies erzwingt die gewünschte Beziehung. (Ziemlich gut, dass man das mit linearen Ungleichungen machen kann, oder?)y1x1+x21y1x1y1x20y11y1

Logisches ODER: Verwenden Sie die linearen Bedingungen , , , , wobei eine ganze Zahl sein muss.y2x1+x2y2x1y2x20y21y2

Logisches NICHT: Verwenden Sie .y3=1x1

Logische Implikation: Um (dh ) , können wir die Konstruktion für das logische ODER anpassen. Verwenden Sie insbesondere die linearen Bedingungen , , , , wobei eine ganze Zahl sein muss.y4=(x1x2)y4=¬x1x2y41x1+x2y41x1y4x20y41y4

Forcierte logische Implikation: Um auszudrücken, dass muss, verwenden Sie einfach die lineare Einschränkung (unter der Annahme, dass und bereits auf boolesche Werte beschränkt sind).x1x2x1x2x1x2

XOR: Um (das Exklusiv-Oder von und ) , verwenden Sie lineare Ungleichungen , , , , , wobei eine ganze Zahl sein muss.y5=x1x2x1x2y5x1+x2y5x1x2y5x2x1y52x1x20y51y5


Und als Bonus eine weitere Technik, die oft hilft, wenn Probleme formuliert werden, die eine Mischung aus null-eins (booleschen) Variablen und ganzzahligen Variablen enthalten:

Umwandlung in Boolean (Version 1): Angenommen, Sie haben eine Ganzzahlvariable und möchten so definieren , dass wenn und wenn . Wenn Sie zusätzlich wissen, dass , können Sie die linearen Ungleichungen , , ; Dies funktioniert jedoch nur, wenn Sie eine Ober- und Untergrenze für . Oder, wenn Sie das wissen ( ) für eine Konstante , dann können Sie die hier beschriebene Methode verwendenxyy=1x0y=0x=00xU0y1yxxUyx|x|UUxUU. Dies gilt nur, wenn Sie eine Obergrenze für.|x|

Cast to Boolean (Version 2): Betrachten wir dasselbe Ziel, aber jetzt kennen wir keine Obergrenze für . Nehmen wir jedoch an, wir wissen, dass . Hier erfahren Sie, wie Sie diese Einschränkung in einem linearen System ausdrücken können. Führen Sie zunächst eine neue Ganzzahlvariable . Addiere Ungleichungen , , . Wählen Sie dann die Zielfunktion, damit Sie minimieren . Dies funktioniert nur, wenn Sie noch keine objektive Funktion hatten. Wenn Sie nicht negative Ganzzahlvariablen und alle in boolesche Werte umwandeln möchten, ist wennxx0t0y1yxt=xytnx1,,xnyi=1xi1 und wenn , dann können Sie Variablen mit Ungleichungen , , und die Zielfunktion definieren um zu minimieren . Dies funktioniert wiederum nur, wenn nichts anderes erforderlich ist, um eine Zielfunktion zu definieren (außer wenn Sie die Machbarkeit des resultierenden ILP auf Boolesche Werte überprüfen und nicht versuchen, eine Funktion der Variablen zu minimieren / maximieren).yi=0xi=0nt1,,tn0yi1yixiti=xiyit1++tn


Für einige exzellente Übungsaufgaben und Beispiele empfehle ich die Formulierung ganzzahliger linearer Programme: A Rogues 'Gallery .

DW
quelle
Welcher lineare Programmierlöser kann dies lösen? Da eine Seite der Einschränkung im * .lp- oder * .mps-Format vorliegt, muss sie eine feste Ganzzahl und keine Variable sein.
Boxi
4
@boxi, ich weiß nichts über das * .lp- oder * .mps-Format, aber jeder ganzzahlige lineare Programmierlöser sollte dies lösen können. Beachten Sie, dass wenn Sie etwas wie , dies gleichbedeutend mit , was möglicherweise in dem von Ihnen gewünschten Format vorliegt. xyyx0
DW
-Ich habe es noch einmal überprüft. lp_solve kann es lösen, aber zum Beispiel kann qsopt nicht. Ich weiß nicht warum. aber danke <3
boxi
@boxi, ich habe gerade die Benutzeroberfläche des QSopt-Online-Applets überprüft und konnte diese Art von Einschränkungen verarbeiten, sobald ich in geändert habe. Ich bin mir also nicht sicher, was los ist. (Ich habe das * .lp-Format verwendet.) Ich wäre überrascht, wenn ein ILP-Solver diese Systeme nicht handhaben könnte. Wenn Sie weitere Fragen zu QSopt haben, sollten Sie diese wahrscheinlich an die QSopt-Support-Foren weiterleiten. xyxy0
DW
1
@Pramod, guten Fang! Vielen Dank, dass Sie diesen Fehler entdeckt haben. Du hast absolut recht. Ich habe eine neue Frage zum Modellieren dieses Falls gestellt und werde diese Antwort aktualisieren, sobald wir eine Antwort auf diese Frage erhalten.
DW
19

Die logische UND-Beziehung kann in einer Bereichsbedingung anstelle von drei Bedingungen (wie in der anderen Lösung) modelliert werden . Anstelle der drei Bedingungen kann die einzige Bereichsbedingung In ähnlicher Weise gilt für logisches ODER:

y1x1+x21,y1x1,y1x2,
0 2 y 1 - x 1 - x 21
0x1+x22y11.
02y1x1x21.

Für NOT ist keine solche Verbesserung verfügbar.

Im Allgemeinen ist für ( Wege-UND) die Einschränkung: Ähnliches gilt für OR: n 0 & Sigma; x i - n y n - 1y=x1x2xnn0 n y - Σ x in - 1

0xinyn1.
0nyxin1.
Abdelmonem Mahmoud Amer
quelle
Ein sehr ähnlicher Ansatz findet sich in diesem Artikel
Abdelmonem Mahmoud Amer
3

Ich habe eine kürzere Lösung für XOR y = x1⊕x2 gefunden (x und y sind binär 0, 1)

nur eine Zeile: x1 + x2 - 2 * z = y (z ist eine beliebige ganze Zahl)

Bysmyyr
quelle
Um die Gleichheit in ILP auszudrücken, benötigen Sie zwei Ungleichungen. Um die Lösung , benötigen Sie zwei weitere Ungleichungen, . Diese Antwort hat also vier Ungleichungen und eine zusätzliche Variable im Vergleich zu sechs Ungleichungen in der Antwort von DW. 0 y 1x1=1,x2=0,z=200,y=1990y1
JiK
Um eine Gleichheit in ILP auszudrücken, ist nur eine Gleichung erforderlich. Dies gilt sowohl für die LP-Theorie als auch für Software wie Gurobi oder CPLEX. @jIk, ich denke, du meinst "zum Ausdruck bringen" a "braucht zwei Ungleichungen."b
Weißgrün