Переменная решения должна находиться в объединении нескольких непересекающихся интервалов.

Question

В моей линейной программе я пытаюсь выразить, что переменная решения $x \in R$ может находиться только в определенных интервалах, например $x \in [0,2] \cup [5,8] \cup [9,15]$.
Я знаю, что вы можете смоделировать либо ограничение 1, либо ограничение 2 с помощью трюка Big M (например, объясненного здесь в разделе 7.3 и заданного здесь , но не вижу напрямую, как это может решить мой вопрос. Есть идеи?

Answer 1

Если $[a_i,b_i]$ это $i$-й интервал тогда для двоичной переменной $z_i$ неравенство

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

дает $x\in[a_i,b_i]$ когда $z_i=1$ и является «бесплатным» ($x\in [-M,M]$) когда $z_i=0$. Итак, семейство таких ограничений вместе с

$$\sum z_i= 1$$

моделирует членство в объединении интервалов $x\in\bigcup_i[a_i,b_i]$.

Answer 2

С такими же двоичными переменными $z_i$ как в ответе @MichalAdamaszek, более жесткая формулировка \begin{align} \sum_i a_i z_i \le x &\le \sum_i b_i z_i \\ \sum_i z_i &= 1 \end{align}