Variável booleana verdadeira se a equação for satisfeita no ILP

Assumindo $y$ é uma variável booleana em um programa ILP (ou seja, $y \in Z$st $0 <= y <= 1$) e $x_1$, $x_2$ são variáveis ​​inteiras delimitadas entre $0$ e $M$. Quero codificar a seguinte restrição de alto nível:

Até agora eu tenho isso:

Isso força que sempre que $x_1 > x_2$ é verdade, $y$ devemos ser $1$ou a equação não será válida. No entanto, se$x_1 \le x_2$, nada está restringindo $y$ e assim poderia ser $0$ ou $1$.

Que outra equação eu poderia adicionar para codificar a restrição?

Você pode fazer isso introduzindo as duas desigualdades

e

O primeiro codifica o requisito $y=1 \implies x_1 \le x_2$ (você pode ver que se $y=1$, então o $M(1-y)$termo desaparece; E se$y=0$, então $M(1-y)$torna-se algo enorme e a desigualdade é automaticamente satisfeita). Este último codifica o requisito$y=0 \implies x_1 > x_2$ (por razões semelhantes).

Espero que isso lhe dê uma idéia de como lidar com outros tipos de implicações também, caso surjam. Basicamente, multiplique por algo grande e adicione / subtraia em algum lugar.

Você pode adicionar uma constante $0<A<M$ e você adiciona esta restrição:

Se , você ficará com$y=1$

E se , você ficará com$y=0$

Observe as restrições de indicadores e as restrições de SOS. Embora você possa definir as relações de destino linearmente como outras respostas explicaram, restrições especiais podem ser tratadas com mais eficiência pelo solucionador de IP.

Se você decidir implementar as restrições diretamente, conforme descrito pela outra resposta, tente usar o menor M possível e considere diminuir a tolerância à integralidade se o resultado não estiver correto. Além disso, para evitar desigualdades estritas, elas são ambíguas no contexto da aritmética de ponto flutuante.

Usando restrições de indicadores:

$x_1\le x_2 \leftarrow y=1$

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

A segunda restrição é equivalente a para números inteiros, se você quiser simplesmente solte o 1.$x_2>x_1$$x_2\ge x_1$