A variável de decisão deve estar na união de vários intervalos disjuntos

Dec 25 2020

Em meu Programa Linear, estou tentando expressar que uma variável de decisão $x \in R$ só pode estar em certos intervalos, por exemplo $x \in [0,2] \cup [5,8] \cup [9,15]$.
Estou ciente de que você pode modelar a restrição 1 OU a restrição 2 com um truque Big M (por exemplo, explicado aqui na seção 7.3 e perguntado aqui , mas não vejo diretamente como isso poderia resolver minha dúvida. Alguma ideia?

Respostas

1 MichalAdamaszek Dec 25 2020 at 16:43

E se $[a_i,b_i]$ é o $i$-ésimo intervalo então para uma variável binária $z_i$ a desigualdade

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

$x\in[a_i,b_i]$ quando $z_i=1$ e é "grátis" ($x\in [-M,M]$) quando $z_i=0$. Portanto, uma família de tais restrições, juntamente com

$$\sum z_i= 1$$

modela a adesão em uma união de intervalos $x\in\bigcup_i[a_i,b_i]$.

2 RobPratt Dec 26 2020 at 11:31

Com as mesmas variáveis ​​binárias $z_i$ como na resposta de @MichalAdamaszek, uma formulação mais rígida é \begin{align} \sum_i a_i z_i \le x &\le \sum_i b_i z_i \\ \sum_i z_i &= 1 \end{align}