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:yyZ0<=y<=1x1x20M

y=1x1x2

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

x1x2+(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 .x1>x2y1x1x2y01

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

Setzer22
la source

Réponses:

5

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

x1x2+M(1y)

et

X1>X2-My.

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=1X1X2y=1M(1-y)y=0M(1-y)y=0X1>X2

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<UNE<M

UNE-y(UNE+M)X1-X2M(1-y).

Si vous vous retrouvez avecy=1

-MX1-X20,
qui dit que .X1X2

Et si alors vous vous retrouverez avecy=0

UNEX1-X2M,
qui dit que (depuis ).X1>X20<UNE<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:

X1X2y=1

X2X1+1y=0

La deuxième contrainte est équivalente à pour les entiers, si vous voulez que supprimez simplement le 1.X2>X1X2X1

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