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

58

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 i1xixi0xi1

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 1x 2 y 3 = ¬ x 1 y i x iy1=x1x2y2=x1x2y3=¬x1yixi

(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.)

DW
la source

Réponses:

66

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?)y1x1+x21y1x1y1x20y11y1

OU logique: utilisez les contraintes linéaires , , , , où est contraint d'être un entier.y2x1+x2y2x1y2x20y21y2

NON logique: Utilisez .y3=1x1

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.y4=(x1x2)y4=¬x1x2y41x1+x2y41x1y4x20y41y4

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).x1x2x1x2x1x2

XOR: pour exprimer (l'exclusif-or de et ), utilisez les inégalités linéaires , , , , , où est contraint d'être un entier.y5=x1x2x1x2y5x1+x2y5x1x2y5x2x1y52x1x20y51y5


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 icixyy=1x0y=0x=00xU0y1yxxUyx|x|UUxUU| 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 sixx0t0y1yxt=xytnx1,,xnyi=1xi1 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).yi=0xi=0nt1,,tn0yi1yixiti=xiyit1++tn


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

DW
la source
quel solveur de programmation linéaire peut résoudre ce problème? En format * .lp ou * .mps, un des côtés de la contrainte doit être un entier fixe et non une variable.
boxi
4
@boxi, je ne connais rien au format * .lp ou * .mps, mais tout solveur de programmation linéaire entier devrait pouvoir résoudre ce problème. Notez que si vous avez quelque chose comme , cela équivaut à , qui peut avoir le format souhaité. xyyx0
DW
-J'ai vérifié à nouveau. lp_solve peut le résoudre, mais par exemple, qsopt ne le peut pas. je ne sais pas pourquoi mais merci <3
boxi
@boxi, je viens de vérifier l'interface graphique de l'applet en ligne QSopt et il pourrait gérer ce type de contraintes une fois que j'ai changé en , je ne suis donc pas sûr de ce qui se passe. (J'ai utilisé le format * .lp.) Je serais surpris de savoir si un solveur ILP était incapable de gérer ces systèmes. Si vous avez d'autres questions sur QSopt, vous devriez probablement les consulter sur les forums d'assistance de QSopt. xyxy0
DW
1
@Pramod, bonne prise! Merci d'avoir repéré cette erreur. Vous avez absolument raison. J'ai posé une nouvelle question sur la façon de modéliser ce cas et je mettrai à jour cette réponse lorsque nous aurons une réponse à cette question.
DW
19

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:

y1x1+x21,y1x1,y1x2,
0x1+x22y11.
02y1x1x21.

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=x1x2xnn

0xinyn1.
0nyxin1.
Abdelmonem Mahmoud Amer
la source
Une approche très similaire est présentée dans cet article: ncbi.nlm.nih.gov/pmc/articles/PMC1865583
Abdelmonem Mahmoud Amer le
3

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)

Bysmyyr
la source
Pour exprimer l'égalité dans ILP, vous avez besoin de deux inégalités. De plus, pour éviter la solution , vous avez besoin de deux autres inégalités, . Donc, cette réponse a quatre inégalités et une variable supplémentaire par rapport à six inégalités dans la réponse de DW. 0 y 1x1=1,x2=0,z=200,y=1990y1
JiK
Pour exprimer une égalité dans ILP, une seule équation est nécessaire, cela est vrai à la fois dans la théorie de la LP et dans des logiciels tels que Gurobi ou CPLEX. @ jIk, je suppose que vous voulez dire que "exprimer" a "nécessite deux inégalités."b
whitegreen