If-Then-ElseIf-Then 혼합 정수 선형 프로그래밍

Question

Python의 PuLP에서 If-Then-Else-If ... 조건을 구성하려고합니다.

나는 MIP에서 If-Then과 If-Then-Else을 보았다. 그러나 선택 사항을 다음 제약 조건 세트로 전파하는 방법과 2 개 이상의 의사 결정 분기를 처리하는 방법을 이해하려고합니다.

는 설명 image shown here에 표시된 조건의 제약을 고려 :

x와 y 내 의사 결정 변수입니다. 나는 간단한 경우 - 당시 다른 상황에 대해 "빅 M"기술을 사용하는 방법을 알고

if x=0: C2>0 
elif x=1: C10>0 
elif x=2: C3>0 

if x=0 and y=0: 
    C4>0; 
    C8>0; 
    C10>0 
elif x=0 and y=1: 
    C5>0; 
    C8>0; 
    C10>0 
elif x=2 and y=0: 
    C6>0; 
    C9>0; 
    C10>0 
elif x=2 and y=1: 
    C7>0; 
    C9>0; 
    C10>0 

:로 는 기본적으로,이 읽습니다. 문제가 있었다면 그래서 예를 들어, : 2 개 이상의 지점이 있다면 그것으로 더 이상 곱셈 없다, 그래서

1. :

   Problem: 
       if (x = 1) then (A < 0) else (B < 0) 
   Solution: 
       problem += A < M1*(1-x) 
       problem += B < M2*x 
   

   내가 이해할 수없는 것은, 어떻게 이것을 변경 x 및 (1-x)이다.

2. 원래 결정 아래에 후속 분기가있는 경우 위에서 결정한 값에 따라 결정이 내려집니다. 그들은 대신 {0, 1}에서의 바이너리 그래서

   가 x 변수를 재구성 :

   FIRST :

Answer 1

정말 여기에 포함 된 세 가지 단계가 있습니다. (엄밀히 말하면, 이것은 필요하지 않습니다,하지만 난 그게 일반화 솔루션 청소기를 만들어 쉽게 생각합니다.)

그래서, 세 개의 새로운 이진 변수 x0, x1, x2을 소개하고 다음과 같이 그들을 제한 :

x0 >= 1 - x 
x0 <= 1 - 0.5x 

x2 >= x - 1 
x2 <= 0.5 x 

x1 = x - 2x2 

그래서 : x = 0 인 경우 처음 두 제약 조건은 x0 = 1이고 두 번째 제약 조건은 x2 = 0이고 마지막 값은 x1 = 0이 필요합니다. 마찬가지로 x = 1 또는 x = 2 인 경우 (내 논리를 다시 확인해야합니다.)

모델에 원래 x 변수와 새로운 2 진 변수가 더해집니다.

SECOND :

가 같아지는, w_ijkl 말,라는 새로운 이진 결정 변수를 생성 한 경우 x0 = i, x1 = j, x2 = k 및 y = l, i를 들어, j, {0,1}에 k, l. 다음과 같은 제약을 통해이 정의를 적용 :

w_ijkl >= i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) + 
      k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y) - 3 
w_ijkl <= 0.25 * [i*x0 + (1-i)*(1-x0) + j*x1 + (1-j)*(1-x1) + 
        k*x2 + (1-k)*(1-x2) + l*y + (1-l)*(1-y)] 

첫 번째 제약은 네 개의 변수 (등 i, j) 자신의 목표를 같게하면 다음 w_ijkl 1과 동일해야하며, 그렇지 않으면 0을 동일 할 수 있다고 말한다.

w_0110 >= 1-x0 + x1 + x2 + (1-y) - 3 
w_0110 <= 0.25 * [1-x0 + x1 + x2 + (1-y)] 

셋째 :

두 번째 제약은 네 개의 동일한 목표물 경우, 다음 w_ijkl는, (1)과 동일 할 수있다, 그렇지 않으면 그래서 0

동일해야 함을 말한다, 예를 들어, w_0110는 이러한 제약을 얻는다

제약 조건을 켜거나 끄려면 big-M을 원하는대로 사용하십시오. 따라서, 예를 들어, C6 >= 0을 필요로하는 x=2 및 y=0 사용하는 경우 :

C6 >= M * (w_0010 - 1) 

(그런데, 일반적으로 당신은 MIP 엄격한 불평등 제약 조건을 사용할 수 없습니다 - 당신이보다 큰-또는 - 필요 같거나보다 작거나 같은 제약 조건)