Expresar operaciones lógicas booleanas en la programación lineal de enteros cero-uno (ILP)

Tengo un programa lineal entero (ILP) con algunas variables que están destinadas a representar valores booleanos. Las están restringidas a ser enteros y a contener 0 o 1 ( ).x i 0 ≤ x i ≤ $x_i$$x_i$$0 \le x_i \le 1$

Quiero expresar operaciones booleanas en estas variables con valor 0/1, usando restricciones lineales. ¿Cómo puedo hacer esto?

Más específicamente, quiero establecer (boolean AND), (boolean OR), y (boolean NOT). Estoy usando la interpretación obvia de 0/1 como valores booleanos: 0 = falso, 1 = verdadero. ¿Cómo escribo las restricciones de ILP para asegurar que las están relacionadas con las como se desea?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$

(Esto podría verse como una solicitud de reducción de CircuitSAT a ILP, o una forma de expresar SAT como ILP, pero aquí quiero ver una forma explícita de codificar las operaciones lógicas que se muestran arriba).

Y lógico: utilice las restricciones lineales , , , , donde está limitado a ser un número entero. Esto hace cumplir la relación deseada. (Bastante claro que puedes hacerlo solo con desigualdades lineales , ¿eh?)$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$

O lógico: utilice las restricciones lineales , , , , donde está limitado a ser un número entero.$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$

NO lógico: utilice .$y_3 = 1-x_1$

Implicación lógica: para expresar (es decir, ), podemos adaptar la construcción para OR lógico. En particular, use las restricciones lineales , , , , donde está limitado a ser un número entero.$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$

Implicación lógica forzada: para expresar que debe , simplemente use la restricción lineal (suponiendo que y ya están restringidas a valores booleanos).$x_1 \Rightarrow x_2$$x_1 \le x_2$$x_1$$x_2$

XOR: Para expresar (el exclusivo-o de y ), utilice desigualdades lineales , , , , , donde está limitado a ser un número entero.$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$

Y, como beneficio adicional, una técnica más que a menudo ayuda a la hora de formular problemas que contienen una mezcla de variables cero-uno (booleanas) y variables enteras:

Cast to boolean (versión 1): suponga que tiene una variable entera , y desea definir para que si e si . Si además sabe que , puede usar las desigualdades lineales , , ; sin embargo, esto solo funciona si conoce un límite superior e inferior en . O, si sabes que (es decir, ) para alguna constante , entonces puede usar el método descrito aquí$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$. Esto solo es aplicable si conoce un límite superior en.$|x|$

Cast to boolean (versión 2): Consideremos el mismo objetivo, pero ahora no conocemos un límite superior en . Sin embargo, supongamos que sabemos que . Aquí le mostramos cómo podría expresar esa restricción en un sistema lineal. Primero, introduzca una nueva variable entera . Agregue desigualdades , , . Luego, elija la función objetivo para minimizar . Esto solo funciona si aún no tenía una función objetivo. Si tiene variables enteras no negativas y desea convertirlas todas en booleanos, de modo que si$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$ e si , entonces puede introducir variables con desigualdades , , y definir la función objetivo para minimizar . Nuevamente, esto solo funciona, nada más necesita definir una función objetivo (si, aparte de los lanzamientos a booleano, planeaba verificar la viabilidad del ILP resultante, no tratar de minimizar / maximizar alguna función de las variables).$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$

Para algunos problemas de práctica excelentes y ejemplos trabajados, recomiendo formular programas lineales enteros: una galería de pícaros .

La relación AND lógica se puede modelar en una restricción de rango en lugar de tres restricciones (como en la otra solución). Entonces, en lugar de las tres restricciones se puede escribir usando la restricción de rango único Del mismo modo, para OR lógico:

Para NO, tal mejora no está disponible.

En general, para ( -way AND) la restricción será: De manera similar para OR: $y=x_1 \land x_2 \land \dots \land x_n$$n$0 ≤ n y - ∑ x i ≤ n -

Encontré una solución más corta para XOR y = x1⊕x2 (x e y son binarios 0, 1)

solo una línea: x1 + x2 - 2 * z = y (z es cualquier número entero)