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

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 i ≤ $x_i$$x_i$$0 \le x_i \le 1$

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 1 ∨ x 2 y 3 = ¬ x 1 y i x $y_1 = x_1 \land x_2$$y_2 = x_1 \lor x_2$$y_3 = \neg x_1$$y_i$$x_i$

(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.)

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?)$y_1 \ge x_1 + x_2 - 1$$y_1 \le x_1$$y_1 \le x_2$$0 \le y_1 \le 1$$y_1$

Logisches ODER: Verwenden Sie die linearen Bedingungen , , , , wobei eine ganze Zahl sein muss.$y_2 \le x_1 + x_2$$y_2 \ge x_1$$y_2 \ge x_2$$0 \le y_2 \le 1$$y_2$

Logisches NICHT: Verwenden Sie .$y_3 = 1-x_1$

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.$y_4 = (x_1 \Rightarrow x_2)$$y_4 = \neg x_1 \lor x_2$$y_4 \le 1-x_1 + x_2$$y_4 \ge 1-x_1$$y_4 \ge x_2$$0 \le y_4 \le 1$$y_4$

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).$x_1 \Rightarrow x_2$$x_1 \le x_2$$x_1$$x_2$

XOR: Um (das Exklusiv-Oder von und ) , verwenden Sie lineare Ungleichungen , , , , , wobei eine ganze Zahl sein muss.$y_5 = x_1 \oplus x_2$$x_1$$x_2$$y_5 \le x_1 + x_2$$y_5 \ge x_1-x_2$$y_5 \ge x_2-x_1$$y_5 \le 2-x_1-x_2$$0 \le y_5 \le 1$$y_5$

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 verwenden$x$$y$$y=1$$x \ne 0$$y=0$$x=0$$0 \le x \le U$$0 \le y \le 1$$y \le x$$x \le Uy$$x$$|x| \le U$$-U \le x \le U$$U$. 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 wenn$x$$x \ge 0$$t$$0 \le y \le 1$$y \le x$$t=x-y$$t$$n$$x_1,\dots,x_n$$y_i=1$$x_i\ge 1$ 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).$y_i=0$$x_i=0$$n$$t_1,\dots,t_n$$0 \le y_i \le 1$$y_i \le x_i$$t_i=x_i-y_i$$t_1+\dots + t_n$

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

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:

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 - $y=x_1 \land x_2 \land \dots \land x_n$$n$0 ≤ n y - Σ x i ≤ n -

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)