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

58

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 i1xixi0xi1

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 1x 2 y 3 = ¬ x 1 y i x iy1=x1x2y2=x1x2y3=¬x1yixi

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

DW
fuente

Respuestas:

66

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?)y1x1+x21y1x1y1x20y11y1

O lógico: utilice las restricciones lineales , , , , donde está limitado a ser un número entero.y2x1+x2y2x1y2x20y21y2

NO lógico: utilice .y3=1x1

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.y4=(x1x2)y4=¬x1x2y41x1+x2y41x1y4x20y41y4

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

XOR: Para expresar (el exclusivo-o de y ), utilice desigualdades lineales , , , , , donde está limitado a ser un número entero.y5=x1x2x1x2y5x1+x2y5x1x2y5x2x1y52x1x20y51y5


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íxyy=1x0y=0x=00xU0y1yxxUyx|x|UUxUU. 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 sixx0t0y1yxt=xytnx1,,xnyi=1xi1 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).yi=0xi=0nt1,,tn0yi1yixiti=xiyit1++tn


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

DW
fuente
¿Qué solucionador de programación lineal puede resolver esto? porque en formato * .lp o * .mps un lado de la restricción tiene que ser un entero fijo y no una variable.
boxi
44
@boxi, no sé nada sobre el formato * .lp o * .mps, pero cada solucionador de programación lineal de enteros debería poder resolver esto. Tenga en cuenta que si tiene algo como , esto es equivalente a , que puede estar en el formato que desea. y - x 0xyyx0
DW
-Lo revisé de nuevo. lp_solve puede resolverlo, pero por ejemplo qsopt no puede. No se porque. pero gracias <3
boxi
@boxi, acabo de comprobar la GUI en línea del applet QSopt y podría manejar este tipo de restricciones una vez que cambie a , así que no estoy seguro de lo que está sucediendo. (Utilicé el formato * .lp.) Me sorprendería si algún solucionador de ILP no pudiera manejar estos sistemas. Si tiene más preguntas sobre QSopt, probablemente debería llevarlas a los foros de soporte de QSopt. x - y 0xyxy0
DW
1
@Pramod, buena captura! Gracias por detectar ese error. Estás absolutamente en lo correcto. He hecho una nueva pregunta sobre cómo modelar ese caso y actualizaré esta respuesta cuando obtengamos una respuesta a esa.
DW
19

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:

y1x1+x21,y1x1,y1x2,
0x1+x22y11.
02y1x1x21.

Para NO, tal mejora no está disponible.

En general, para ( -way AND) la restricción será: De manera similar para OR: y=x1x2xnn0 n y - x in - 1

0xinyn1.
0nyxin1.
Abdelmonem Mahmoud Amer
fuente
Un enfoque muy similar se encuentra en este documento: ncbi.nlm.nih.gov/pmc/articles/PMC1865583
Abdelmonem Mahmoud Amer
3

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)

Bysmyyr
fuente
Para expresar la igualdad en ILP, necesita dos desigualdades. Además, para evitar la solución , necesita dos desigualdades más, . Entonces, esta respuesta tiene cuatro desigualdades y una variable adicional en comparación con seis desigualdades en la respuesta de DW. 0 y 1x1=1,x2=0,z=200,y=1990y1
JiK
Para expresar una igualdad en ILP solo se necesita una ecuación, esto es cierto tanto en la teoría LP como en software como Gurobi o CPLEX. @jIk, supongo que quieres decir que "expresar" a "necesita dos desigualdades".b
whitegreen