결정 변수는 여러 개의 분리 된 간격의 합집합에 있어야합니다.

Dec 25 2020

선형 프로그램에서 결정 변수를 표현하려고합니다. $x \in R$ 특정 간격으로 만 놓일 수 있습니다. 예 : $x \in [0,2] \cup [5,8] \cup [9,15]$.
난 당신이 모델링 할 수 있음을 알고 있어요 하나 제약 (1) 또는 제약 (2) (예를 들어 큰 M 트릭과 여기에 7.3에서 설명 하고 여기에 질문 ,하지만 내 질문을 해결할 수있는 방법에 대해 설명합니다. 어떤 아이디어를 직접 표시되지 않는 이유는 무엇입니까?

답변

1 MichalAdamaszek Dec 25 2020 at 16:43

만약 $[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]$.

2 RobPratt Dec 26 2020 at 11:31

동일한 이진 변수 사용 $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}