Puede convertir cualquier restricción de desigualdad en una restricción de igualdad, pero eso producirá una nueva restricción de desigualdad. Suponga que tiene la siguiente restricción de desigualdad:
[matemáticas] a_ {1,1} x_1 + a_ {1,2} x_2 + \ cdots + a_ {1, n} x_n \ le b_1 [/ matemáticas].
Puede definir una variable de holgura s1 tal que:
- Cómo aprender machine learning con experiencia en negocios
- ¿Cuál es la mejor descripción del cálculo lambda?
- Cómo aumentar la velocidad de cálculo de la función trigonométrica en una computadora
- Cómo resolver [matemáticas] (n + k) ^ j = \ Theta (n ^ j) [/ matemáticas] para k, j en números reales y j> 0
- ¿Es P vs NP el problema más difícil e importante del Premio del Milenio?
[matemáticas] a_ {1,1} x_1 + a_ {1,2} x_2 + \ cdots + a_ {1, n} x_n + s_1 = b_1 [/ matemáticas].
Pero la segunda restricción no es suficiente por sí misma. Debe restringir la variable de holgura, de acuerdo con la diferencia entre el original menos la nueva restricción:
[matemáticas] – s_1 \ le 0 [/ matemáticas].
Esto significa que la variable de holgura no debe ser negativa. Esto significa que volvemos a las desigualdades. El documento que vinculó (LinOpt4.pdf) dice que [math] Ax = b [/ math] es polinomial para enteros, pero NP-completo para números naturales (enteros con> = 1). Esto significa que la adición de una variable de holgura no negativa hace que este problema sea NP completo.
¿Por qué las restricciones de enteros con desigualdad son NP-completas?
En primer lugar, es trivial mostrar que la comprobación de la validez de la restricción de la solución se puede hacer en tiempo polivinílico. Entonces, hay una reducción trivial de CNF (el problema SAT) al problema de las restricciones de enteros con desigualdad. La reducción es la siguiente:
Para simplificar, en lugar de una definición formal de la traducción de CNF, solo daré un ejemplo de cláusula y su conversión:
[matemáticas] (z_1 \ tierra z_2 \ tierra z_3) \ lor (\ neg z_2 \ tierra \ neg z_3 \ tierra z_4) [/ matemáticas].
- Para cada variable booleana [math] z_i [/ math], cree una variable entera [math] x_i [/ math]. Un valor verdadero en [math] z_i [/ math] se asigna a 1 para [math] x_i [/ math]. Y mapas falsos a 0.
- Agregue dos restricciones para cada variable, de modo que [math] 0 \ le x_i \ le 1 [/ math].
- Cada término se convierte por separado y se introduce una nueva variable representativa.
[matemáticas] x_1 + x_2 + x_3 – 3 t_1 \ ge 0 [/ matemáticas]
Donde [math] t_1 [/ math] también está limitado al rango [0, 1].
Tiene 3 como coeficiente, ya que este es el valor máximo de [matemáticas] x_1 + x_2 + x_3 [/ matemáticas] - El segundo término, [math] \ neg z_2 \ land \ neg z_3 \ land z_4 [/ math], se convierte de manera similar a
[matemáticas] -x_2 – x_3 + x_4 – 1 t_2 \ ge 0 [/ matemáticas].
Tiene 1 como coeficiente, ya que este es el valor máximo posible de la parte izquierda de la expresión. - Y finalmente, la restricción para representar la cláusula completa es: [math] t_1 + t_2 \ ge 1 [/ math]. Esto asegura que al menos uno de los términos [matemática] t_1, t_2 [/ matemática] se asignará con 1. Esta asignación de 1 al término, obliga a que el término se cumpla.
- Tenga en cuenta que la asignación de 0 a una variable de término no significa que el término no esté satisfecho. Solo significa que no nos importa si está satisfecho o no, en esa solución en particular.
Esta reducción me tomó alrededor de 1 minuto para entender y 20 minutos para escribir, así que estoy seguro de que hay mejores reducciones para este problema. Por “mejor” quiero decir: más corto y más fácil de seguir. Estoy seguro de que si cavas un poco, encontrarás algo mejor en Internet. Y si no es más agradable, con una definición más formal (sin recurrir a ejemplos como lo hice yo).