Quiero expresar la siguiente restricción, en un programa lineal entero:
Ya tengo las variables enteras y me prometieron que . ¿Cómo puedo expresar la restricción anterior, en una forma adecuada para usar con un solucionador de programación lineal entero?
Presumiblemente, esto requerirá la introducción de algunas variables adicionales. ¿Qué nuevas variables y restricciones necesito agregar? ¿Se puede hacer limpiamente con una nueva variable? ¿Dos?
De manera equivalente, esto es preguntar cómo hacer cumplir la restricción
en el contexto donde ya tengo restricciones que implican y .
(Mi objetivo es corregir un error en /cs//a/12118/755 ).
Respuestas:
Creo que puedo hacerlo con una variable binaria adicional :δ∈{0,1}
Actualizar
Esto supone que es una variable continua . Si restringimos para que tenga un valor entero , entonces la segunda restricción se puede simplificar a:x x y - 101 δ ≤ x ≤ - y + 101 ( 1 - δ )x y−101δ≤x≤−y+101(1−δ)
fuente
Lo siguiente no es bonito de ninguna manera, pero funciona. Sea , en el caso específico de la pregunta. Entonces tenemos las siguientes restricciones.N = 1000≤x≤N N=100
La intuición es la siguiente. . Esto está codificado en las restricciones 2 y 3. De manera similar, las restricciones 4 y 5 codifican . Las últimas tres restricciones expresan .z1=1⟺x≤0 z2=1⟺x≥0 z=z1∧z2
fuente
Aquí hay una solución que usa dos variables temporales. Supongamos que sea una variable entera de cero o uno, con el significado deseado de que si , si , y . Estos pueden hacerse cumplir con las siguientes restricciones:t,u t=1 x≥0 u=1 x≤0 y=¬(t∧u)
fuente