Opérations logiques booléennes expresses en programmation linéaire zéro entier (ILP)

J'ai un programme linéaire entier (ILP) avec des variables destinées à représenter des valeurs booléennes. Les sont contraints d'être des entiers et de contenir 0 ou 1 ( ).x i 0 ≤ x i ≤ $x_i$$x_i$$0 \le x_i \le 1$

Je veux exprimer des opérations booléennes sur ces variables à valeur 0/1, en utilisant des contraintes linéaires. Comment puis-je faire ceci?

Plus précisément, je souhaite définir (booléen ET), (booléen OU) et (booléen NON). J'utilise l'interprétation évidente de 0/1 en tant que valeurs booléennes: 0 = faux, 1 = vrai. Comment puis-je écrire des contraintes ILP pour m'assurer que les sont liés aux comme souhaité?y 2 = x 1 ∨ x 2 y 3 = ¬ x 1 y i x $y_1 = x_1 \land x_2$$y_2 = x_1 \lor x_2$$y_3 = \neg x_1$$y_i$$x_i$

(Cela pourrait être perçu comme demandant une réduction de CircuitSAT à ILP ou un moyen d'exprimer SAT en tant que ILP, mais je souhaite ici voir un moyen explicite de coder les opérations logiques présentées ci-dessus.)

ET logique: Utilisez les contraintes linéaires , , , , où est contraint d'être un entier. Cela renforce la relation souhaitée. (Assez chouette de pouvoir le faire avec juste des inégalités linéaires , hein?)$y_1 \ge x_1 + x_2 - 1$$y_1 \le x_1$$y_1 \le x_2$$0 \le y_1 \le 1$$y_1$

OU logique: utilisez les contraintes linéaires , , , , où est contraint d'être un entier.$y_2 \le x_1 + x_2$$y_2 \ge x_1$$y_2 \ge x_2$$0 \le y_2 \le 1$$y_2$

NON logique: Utilisez .$y_3 = 1-x_1$

Implication logique: Pour exprimer (c'est-à-dire ), nous pouvons adapter la construction au OU logique. En particulier, utilisez les contraintes linéaires , , , , où est contraint d'être un entier.$y_4 = (x_1 \Rightarrow x_2)$$y_4 = \neg x_1 \lor x_2$$y_4 \le 1-x_1 + x_2$$y_4 \ge 1-x_1$$y_4 \ge x_2$$0 \le y_4 \le 1$$y_4$

Implication logique forcée: pour exprimer ce que doit tenir, utilisez simplement la contrainte linéaire (en supposant que et sont déjà contraints à des valeurs booléennes).$x_1 \Rightarrow x_2$$x_1 \le x_2$$x_1$$x_2$

XOR: pour exprimer (l'exclusif-or de et ), utilisez les inégalités linéaires , , , , , où est contraint d'être un entier.$y_5 = x_1 \oplus x_2$$x_1$$x_2$$y_5 \le x_1 + x_2$$y_5 \ge x_1-x_2$$y_5 \ge x_2-x_1$$y_5 \le 2-x_1-x_2$$0 \le y_5 \le 1$$y_5$

Et, en prime, une technique supplémentaire qui aide souvent lors de la formulation de problèmes qui combinent des variables zéro-un (booléennes) et des variables entières:

Conversion en booléen (version 1): supposons que vous ayez une variable entière et que vous vouliez définir pour que si et si . Si vous savez en outre que , vous pouvez utiliser les inégalités linéaires , , ; Cependant, cela ne fonctionne que si vous connaissez une limite supérieure et inférieure sur . Ou, si vous savez que (c’est ) pour une constante , vous pouvez utiliser la méthode décrite ici$x$$y$$y=1$$x \ne 0$$y=0$$x=0$$0 \le x \le U$$0 \le y \le 1$$y \le x$$x \le Uy$$x$$|x| \le U$$-U \le x \le U$$U$| x |. Ceci n'est applicable que si vous connaissez une limite supérieure sur.$|x|$

Cast to boolean (version 2): Considérons le même objectif, mais nous ne connaissons pas de limite supérieure sur . Cependant, supposons que nous savons que . Voici comment vous pourriez pouvoir exprimer cette contrainte dans un système linéaire. Premièrement, introduisez une nouvelle variable entière . Ajouter des inégalités , , . Ensuite, choisissez la fonction objectif afin de minimiser . Cela ne fonctionne que si vous n'avez pas déjà une fonction objectif. Si vous avez variables entières non négatives et que vous souhaitez toutes les convertir en booléens, de sorte que si$x$$x \ge 0$$t$$0 \le y \le 1$$y \le x$$t=x-y$$t$$n$$x_1,\dots,x_n$$y_i=1$$x_i\ge 1$ et si , vous pouvez introduire variables avec des inégalités , , et définir la fonction objectif minimiser . Encore une fois, cela ne fonctionne que pour que rien ne définisse une fonction objective (si, en dehors des transtypes en booléens, vous envisagiez de vérifier simplement la faisabilité du PIL résultant, n'essayez pas de minimiser / maximiser certaines fonctions des variables).$y_i=0$$x_i=0$$n$$t_1,\dots,t_n$$0 \le y_i \le 1$$y_i \le x_i$$t_i=x_i-y_i$$t_1+\dots + t_n$

Pour certains problèmes pratiques excellents et des exemples concrets, je vous recommande Formuler des programmes linéaires entiers: une galerie de voleurs .

La relation AND logique peut être modélisée dans une contrainte de plage au lieu de trois contraintes (comme dans l'autre solution). Ainsi, au lieu des trois contraintes il peut être écrit à l'aide de la contrainte de plage unique De même, pour le OU logique:

Pour NOT, aucune amélioration n'est disponible.

En général pour ( -way AND), la contrainte sera la suivante: De même pour OR: $y=x_1 \land x_2 \land \dots \land x_n$$n$

J'ai trouvé une solution plus courte pour XOR y = x1⊕x2 (x et y sont binaires 0, 1)

juste une ligne: x1 + x2 - 2 * z = y (z est un entier)