Entiendo el problema 3-Sat pero no entiendo el Programa Lineal Entero 0-1. Sé que en un programa entero lineal tendría una variable indicadora $X_i$ que indica si una cláusula es verdadera o no, y quiero maximizar esto? ¿Puede alguien mostrarme cómo representar este problema como un programa entero lineal 0-1?
Respuesta
¿Demasiados anuncios?
Existen dos versiones del problema del Programa Lineal Entero: una versión de decisión y una versión de optimización. La versión de decisión sólo pregunta si hay cualquier solución entera al conjunto de ecuaciones; el problema de optimización pregunta si existe una solución que optimice/maximice alguna función objetivo.
En decisión ("¿hay alguna solución entera para este conjunto de ecuaciones?") es la que equivale a 3SAT. (Tenga en cuenta que 3SAT en sí es un problema de decisión, preguntando si hay alguna solución).
Si eso es todo lo que necesitas para empezar, ignora el resto de la respuesta.
He aquí cómo reducir 3SAT a ILP:
-
Se le da un problema 3SAT en forma de variables como $x_1,\ldots, x_n$ y cláusulas de tres términos que implican esas variables, como $a_1 = (x_1 \vee \overline x_4 \vee \overline{x_7})$ . Una solución a un problema 3SAT es una asignación de valores booleanos a las variables $x_1,\ldots, x_n$ de tal manera que cada cláusula sea verdadera.
-
Se puede hacer un problema ILP correspondiente.
-
Para cada variable $x_i$ en el problema 3SAT, hay una variable $z_i$ en el problema ILP.
-
Por defecto, a las variables de un problema ILP se les puede asignar cualquier valor entero. Para forzar cada variable $z_i$ sea 0 ó 1 (en lugar de un número entero cualquiera), puede introducir las restricciones $$0 \leq z_1 \leq 1$$ $$0 \leq z_2 \leq 1$$ $$\vdots$$ $$0 \leq z_n \leq 1$$ al problema ILP.
-
Ahora tenemos que traducir las cláusulas booleanas como $a = (x_1 \vee \overline x_4 \vee \overline{x_7})$ en ecuaciones lineales enteras. Podemos traducirlas sistemáticamente así: $$x_1 \vee \overline{x_4} \vee \overline{x_7} \quad\iff\quad z_1 + (1-z_4) + (1-z_7) > 0$$ Aquí, hemos reemplazado cada término negado $\overline{x_i}$ con $(1-z_i)$ ; hemos reemplazado cada término no negado $x_j$ con $z_j$ y hemos sustituido bitwise-o $(\vee)$ con adición (+). Esto funciona porque nuestras restricciones anteriores ya obligan al $z_i$ sea 0 o 1, por lo que $(1-z_i)$ tiene el mismo efecto que la negación bitwise, y la suma de un grupo de términos es 0 si todos ellos son 0, o positiva si alguno de ellos es positivo.
-
Utilizando esta estrategia de traducción, puede añadir una nueva restricción lineal al ILP para cada cláusula del problema 3SAT.
-
Los dos problemas son ahora equivalentes: hay una solución entera a este ILP si y sólo si hay una solución booleana al problema 3SAT original.
-
Ejemplo de un problema de decisión 3SAT:
¿Existe una asignación de valores booleanos a las variables $x_1,x_2,x_3,x_4$ de forma que las cláusulas $$A = (x_1 \vee \overline{x_3}\vee x_4)$$ y $$B = (\overline{x_1}\vee \overline{x_2} \vee x_3)$$ se satisfacen simultáneamente?
La instancia ILP equivalente correspondiente:
¿Existe una asignación de valores enteros a las variables $z_1, z_2, z_3, z_4$ tal que el lineal e \begin{align*} 0 & \leq z_1 \leq 1 & \\ 0 & \leq z_2 \leq 1 &\\ 0 & \leq z_3 \leq 1 & \\ 0 & \leq z_4 \leq 1 & \\ \\ &z_1 + (1-z_3) + z_4 > 0 & \qquad [A]\\ &(1-z_1) + (1-z_2) + z_3 > 0 & \qquad [B] \end{align*} se satisfacen simultáneamente?
