Variable booleana verdadera si la ecuación se cumple en ILP

Asumiendo $y$ es una variable booleana en un programa ILP (es decir $y \in Z$, S t $0 <= y <= 1$) y $x_1$, $x_2$ son variables enteras limitadas entre $0$ y $M$. Quiero codificar la siguiente restricción de alto nivel:

Hasta ahora tengo esto:

Esto impone que siempre que $x_1 > x_2$ es verdad, $y$ debe ser $1$o la ecuación no se mantendrá. Sin embargo, si$x_1 \le x_2$nada es restrictivo $y$ y así podría ser $0$ o $1$.

¿Qué otra ecuación podría agregar para codificar la restricción?

Puedes hacer esto introduciendo las dos desigualdades

y

El primero codifica el requisito $y=1 \implies x_1 \le x_2$ (puedes ver que si $y=1$, entonces el $M(1-y)$el término desaparece; Si$y=0$, entonces $M(1-y)$se convierte en algo enorme y la desigualdad se satisface automáticamente). Este último codifica el requisito$y=0 \implies x_1 > x_2$ (por razones similares)

Con suerte, esto le dará una idea de cómo manejar otros tipos de implicaciones también, en caso de que surjan. Básicamente, multiplique por algo grande y agréguelo / reste en alguna parte.

Podrías agregar una constante $0<A<M$ y luego agregas esta restricción:

Si entonces te queda con$y=1$

Y si entonces te quedarás con$y=0$

Examine las restricciones de indicadores y las restricciones de SOS. Si bien puede definir las relaciones de destino linealmente como lo han explicado otras respuestas, el solucionador de IP puede manejar las restricciones especiales de manera más eficiente.

Si decide implementar las restricciones directamente como se describe en la otra respuesta, intente usar la M más pequeña posible y considere reducir la tolerancia de integralidad si su resultado no es correcto. Además, evite las desigualdades estrictas, son ambiguas en el contexto de la aritmética de coma flotante.

Uso de restricciones de indicador:

$x_1\le x_2 \leftarrow y=1$

$x_2\ge x_1 +1\leftarrow y=0$

La segunda restricción es equivalente a para enteros, si desea simplemente suelte el 1.$x_2>x_1$$x_2\ge x_1$