Die Entscheidungsvariable muss in der Vereinigung mehrerer disjunkter Intervalle liegen

Dec 25 2020

In meinem linearen Programm versuche ich, diese Entscheidungsvariable auszudrücken $x \in R$ kann nur in bestimmten Intervallen liegen, z $x \in [0,2] \cup [5,8] \cup [9,15]$.
Mir ist bewusst, dass Sie entweder Einschränkung 1 oder Einschränkung 2 mit einem Big M-Trick modellieren können (z. B. hier in Abschnitt 7.3 erläutert und hier gefragt , aber nicht direkt sehen, wie dies meine Frage lösen könnte. Irgendwelche Ideen?

Antworten

1 MichalAdamaszek Dec 25 2020 at 16:43

Wenn $[a_i,b_i]$ ist der $i$-th Intervall dann für eine binäre Variable $z_i$ die Ungleichung

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

gibt $x\in[a_i,b_i]$ wann $z_i=1$ und ist "frei" ($x\in [-M,M]$) wann $z_i=0$. Also eine Familie solcher Zwänge zusammen mit

$$\sum z_i= 1$$

modelliert die Mitgliedschaft in einer Vereinigung von Intervallen $x\in\bigcup_i[a_i,b_i]$.

2 RobPratt Dec 26 2020 at 11:31

Mit den gleichen binären Variablen $z_i$ Wie in der Antwort von @ MichalAdamaszek ist eine strengere Formulierung \begin{align} \sum_i a_i z_i \le x &\le \sum_i b_i z_i \\ \sum_i z_i &= 1 \end{align}