La variable booléenne vraie équation ssi est satisfaite dans ILP

8

En supposant est une variable booléenne dans un programme d'ILP (qui est , r ) et , sont délimités entier variables entre et . Je veux encoder la contrainte de haut niveau suivante: $y$ $y \in Z$ $0 <= y <= 1$ $x_1$ $x_2$ $0$ $M$

y = 1 ⟺ x_{1} \leq x_{2}

$y = 1 \iff x_1 \le x_2$

Jusqu'à présent, j'ai ceci:

x_{1} \leq x_{2} + (M + 1) y

$x_1 \le x_2 + (M+1)y$

Cela impose que chaque fois que est vrai, doit être ou l'équation ne tiendra pas. Cependant, si , rien ne restreint et pourrait donc être ou . $x_1 > x_2$ $y$ $1$ $x_1 \le x_2$ $y$ $0$ $1$

Quelle autre équation pourrais-je ajouter pour encoder la contrainte?

integer-programming Setzer22
la source

cs.stackexchange.com/q/104990/755

DW

5

Vous pouvez le faire en introduisant les deux inégalités

x_{1} \leq x_{2} + M (1 - y)

$x_1 \le x_2 + M (1-y)$

et

X_{1} > X_{2} - M y .

$x_1 > x_2 - M y.$

Le premier code pour l'exigence (vous pouvez voir que si , alors le terme disparaît; si , alors devient quelque chose d'énorme et l'inégalité est automatiquement satisfaite). Ce dernier code pour l'exigence (pour des raisons similaires). $y=1 \implies x_1 \le x_2$ $y=1$ $M(1-y)$ $y=0$ $M(1-y)$ $y=0 \implies x_1 > x_2$

J'espère que cela vous donnera une idée de la façon de gérer d'autres types d'implications, le cas échéant. Fondamentalement, multipliez par quelque chose de grand et ajoutez-le / soustrayez-le quelque part.

DW
la source

4

Vous pouvez ajouter une constante , puis vous ajoutez cette contrainte: $0<A<M$

UNE - y (UNE + M) ⩽ X_{1} - X_{2} ⩽ M (1 - y) .

$A-y(A+M)\leqslant x_1-x_2\leqslant M(1-y).$

Si vous vous retrouvez avec $y=1$

- M ⩽ X_{1} - X_{2} ⩽ 0,

$-M\leqslant x_1-x_2\leqslant 0,$ qui dit que .

x_{1} ⩽ x_{2}

$x_1\leqslant x_2$

Et si alors vous vous retrouverez avec $y=0$

UNE ⩽ X_{1} - X_{2} ⩽ M,

$A\leqslant x_1-x_2\leqslant M,$ qui dit que (depuis ).

x_{1} > x_{2}

$x_1>x_2$

0 < A < M

$0<A<M$

Ribz
la source

3

Examinez les contraintes d'indicateur et les contraintes SOS. Bien que vous puissiez définir les relations cibles de manière linéaire comme d'autres réponses l'ont expliqué, les contraintes spéciales peuvent être gérées plus efficacement par le solveur IP.

Si vous décidez d'implémenter les contraintes directement comme décrit dans l'autre réponse, essayez d'utiliser le plus petit M possible et envisagez de réduire la tolérance d'intégralité si votre résultat n'est pas correct. Aussi, évitez les inégalités strictes, elles sont ambiguës dans le contexte de l'arithmétique à virgule flottante.

Utilisation de contraintes d'indicateur:

$x_1\le x_2 \leftarrow y=1$

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

La deuxième contrainte est équivalente à pour les entiers, si vous voulez que supprimez simplement le 1. $x_2>x_1$ $x_2\ge x_1$

Septimus G
la source

Merci pour les suggestions utiles! Pouvez-vous expliquer en quoi les contraintes SOS sont utiles / utiles dans cette situation particulière?

DW

J'ai ajouté un exemple avec des contraintes d'indicateur. Pour SOS, c'est plus compliqué et vous devez introduire des variables supplémentaires, vous risquez donc de ne pas gagner beaucoup en les utilisant. Je pense que le seul aspect auquel il faut faire attention ici sont les problèmes numériques qui peuvent survenir en utilisant les formulations proposées par d'autres, et comment les atténuer. Si vous avez accès à un solveur avec des contraintes d'indicateur, essayez-le de cette façon car le solveur peut se brancher directement sur eux ou modifier dynamiquement la valeur big-M.

Septimus G

La variable booléenne vraie équation ssi est satisfaite dans ILP

Réponses: