La variable de décision doit se trouver dans l'union de plusieurs intervalles disjoints

Question

Dans mon programme linéaire, j'essaie d'exprimer qu'une variable de décision $x \in R$ ne peut se trouver que dans certains intervalles, par exemple $x \in [0,2] \cup [5,8] \cup [9,15]$.
Je suis conscient que vous pouvez modéliser soit la contrainte 1 OU la contrainte 2 avec une astuce Big M (par exemple expliqué ici dans la section 7.3 et posé ici , mais ne voyez pas directement comment cela pourrait résoudre ma question. Des idées?

Answer 1

Si $[a_i,b_i]$ est le $i$-ème intervalle alors pour une variable binaire $z_i$ l'inégalité

$$a_iz_i-(1-z_i)M\leq x\leq b_iz_i+(1-z_i)M$$

donne $x\in[a_i,b_i]$ quand $z_i=1$ et est "gratuit" ($x\in [-M,M]$) quand $z_i=0$. Donc, une famille de telles contraintes avec

$$\sum z_i= 1$$

modélise l'appartenance à une union d'intervalles $x\in\bigcup_i[a_i,b_i]$.

Answer 2

Avec les mêmes variables binaires $z_i$ comme dans la réponse de @ MichalAdamaszek, une formulation plus stricte est \begin{align} \sum_i a_i z_i \le x &\le \sum_i b_i z_i \\ \sum_i z_i &= 1 \end{align}