Cast en booléen, pour une programmation linéaire entière

11

Je veux exprimer la contrainte suivante, dans un programme linéaire entier:

y={0if x=01if x0.

J'ai déjà les variables entières et on me promet que . Comment puis-je exprimer la contrainte ci-dessus, sous une forme adaptée à une utilisation avec un solveur de programmation linéaire entier?- 100 x 100x,y100x100

Cela nécessitera probablement l'introduction de variables supplémentaires. Quelles nouvelles variables et contraintes dois-je ajouter? Peut-il être fait proprement avec une nouvelle variable? Deux?

De manière équivalente, cela demande comment faire respecter la contrainte

y0 if and only if x0.

dans le contexte où j'ai déjà des contraintes qui impliquent et .0 y 1|x|1000y1


(Mon objectif est de corriger une erreur dans https://cs.stackexchange.com/a/12118/755 .)

DW
la source
1
Qu'as-tu essayé? Avez-vous essayé de travailler à travers quelques exemples pour voir si vous voyez un motif? Si oui, avez-vous essayé de faire une supposition, puis avez-vous essayé de le prouver?
Brika
1
Il h! Je vois ce que tu as fait là-bas , @Brika. Si vous êtes curieux de voir ce que j'ai essayé, voyez ici ainsi que cette explication de la raison pour laquelle cela était mal . Si vous voulez voir ma prochaine tentative, voyez ma réponse . Merci d'avoir lu mes anciennes questions, et si elles peuvent être améliorées pour l'avenir, j'aimerais entendre toutes les suggestions que vous pourriez avoir!
DW
C'est très bien. ;)
Brika

Réponses:

4

Je pense que je peux le faire avec une variable binaire supplémentaire :δ{0,1}

100yx100y
0.001y100.001δx0.001y+100.001(1δ)

Mettre à jour

Cela suppose que est une variable continue . Si nous limitons à une valeur entière , alors la deuxième contrainte peut être simplifiée en: xx y - 101 δ x - y + 101 ( 1 - δ )x

y101δxy+101(1δ)

Erwin Kalvelagen
la source
1
J'ai vérifié cela correctement en le testant de manière exhaustive avec un petit programme. Merci pour la solution!
DW
@ErwinKalvelagen, pourriez-vous s'il vous plaît expliquer votre logique avec la variable binaire delta, pour un cas plus général, par exemple, si y = {a: x> 0, b: x <0}.
Nick
1
@Nick La variable binaire est utilisée pour modéliser une construction 'OU'. Voir ici pour une réponse à votre question.
Erwin Kalvelagen
@ErwinKalvelagen, la grande réponse, j'ai essayé d'appliquer l'approche de votre à ma question ici cs.stackexchange.com/questions/64794/… .
Nick
1
@GonzaloSolera En fait, j'avais tort: ​​j'ai supposé que était une variable continue. En effet, lorsque est une valeur entière, nous pouvons déplacer de 0,001 à 1 comme vous l'avez suggéré. xxx
Erwin Kalvelagen
1

Ce qui suit n'est pas joli du tout, mais cela fonctionne. Soit , N = 100 dans le cas spécifique de la question. Ensuite, nous avons les contraintes suivantes.0xNN=100

  1. 0z1,z2,z1
  2. xN(1z1)0
  3. xNz11
  4. xN(1z2)0
  5. xNz21
  6. z1+z21z
  7. zz1
  8. zz2

z1=1x0z2=1x0z=z1z2

Pramod
la source
z=1yx=100y=1z=0z1,z2xNz21x<Nx99x=99y=1y=0xNxN0xN
1

t,ut=1x0u=1x0y=¬(tu)

0t,u,y11+x101t101+x1x101u101xt+u11y1yt1yu
DW
la source
x99x100x99
@TLW, merci d'avoir attrapé ça! J'ai modifié ma réponse pour corriger le bogue. Je l'ai testé de manière exhaustive avec un petit programme et je pense qu'il devrait être correct maintenant.
DW