bloc de variables consécutives devant avoir la même valeur dans la programmation linéaire en nombres entiers mixtes

Question

J'essaie de modéliser le fonctionnement d'un composant du système. Le composant aura deux modes de fonctionnement, appelons-les 1 et 2, plus le mode de repos 0.

Il n'y a pas de limite au ralenti, mais chaque mode de fonctionnement durera exactement 3 points de série temporelle, donc x_{i}= 1 signifie x_{i+1} = x_{i+2} = 1 (je ne peux pas afficher d'images, veuillez utiliser le lien ci-dessous pour l'équation). mode de fonctionnement 1

Il en va de même pour le mode de fonctionnement 2.

Par exemple. 011102220 est valide, mais 01110220 ne l'est pas.

111111 ou 222222 ne sont pas valides, mais cela est pris en compte dans d'autres contraintes liées aux ressources (le système n'aura pas assez de ressources pour fonctionner pour plus de 3 points de série temporelle), donc tant que le problème concernant le forçage de trois 1 ou 2 consécutifs dans le tableau de variables est abordé, cela devrait aller.

Merci d'avance,

Answer 1

Les séries de longueur exactement égale à trois peuvent être modélisées comme suit :

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)
1-y(t+3) >= y(t)-y(t-1)

où y(t) est une variable binaire. Les séries de longueur au moins égale à trois peuvent être modélisées en abandonnant la dernière contrainte :

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)

Answer 2

Simplifions quelque peu le problème : nous supposons que nous n'avons que des valeurs binaires, c'est-à-dire que nous ne nous intéressons qu'aux 0 et aux 1.

Introduire un nouveau vecteur binaire auxiliaire start_block . Ce vecteur marque débuts de nouveaux blocs.

Une valeur non nulle dans ce vecteur binaire fait partie des contraintes, qui définissent l'implication d'un bloc.

Appelons le vecteur-solution X .

L'implication se fait par paire.

# zero-order logic
start_block[x] -> X[x]
start_block[x] -> X[x+1]
start_block[x] -> X[x+2]

<=> 

# zero-order logic ( a->b <-> !a V b )
!start_block[x] V X[x]
!start_block[x] V X[x+1]
!start_block[x] V X[x+2]

<=>

# linear expression
(1 - start_block[x]) + X[x] >= 1
(1 - start_block[x]) + X[x+1] >= 1  
(1 - start_block[x]) + X[x+2] >= 1 

Faites cela pour toute la dimension des variables de décision de X (se souciant des frontières).

Gardez à l'esprit que cela dit seulement : s'il y a un 1 dans X il fait partie d'un bloc de taille >=3. Il peut s'agir d'un bloc de 4. Comme je ne connais pas exactement votre modèle, c'est l'approche la plus générale que je peux vous proposer. Bien sûr, vous pouvez encore l'adapter à votre cas !

Généraliser cela pour les variables entières ne devrait pas être trop difficile, mais pourrait introduire de nouvelles variables auxiliaires.