Integer Linear Programming & binary variables (+ Fixed Charge Problem)

Integer Linear Programming 이란?

 

 

Integer Linear Programming 은 Linear 중 Integer 

즉, 정수를 다루는 프로그래밍입니다.

 

위 표에서 따지면 discrete(분절)에 해당하겠네요.

(continuous는 연속적 상태)

(ex: 사람은 1명, 2명 vs 물은 3.123L)

 

-덧-

 

(1) LP Relaxation

 

기존 LP (ILP)에서 정수여야한다라는

제약식 하나 빼주는 거 (이러면 LP가 되기 때문)

 

binary variables 이란?

 

Interger 중에서 0 또는 1의 변수를 갖는  Variable 입니다.

하던지 말던지. 얻던지 잃던지 ox에 활용합니다.(이진수)

 

 

실전 활용

 

<Integer Linear>

 

해 찾기 매개 변수까지의 과정은 

앞 선 포스팅을 참고하시고요.

 

Integer를 제한 조건에 추가 시켜야 합니다.

위 화면 처럼 = 정수가 나와야 합니다.

 

추가에서 변수 포함에 INT를 추가해 줍니다.

 

 

해법 선택 옆 옵션에서는 

정수 제한 조건 무시가 있으면 해제하고

정수 최적화 비율을 낮게 잡을 수록 자세합니다.

 

 

<binary variables>

 

 

binary variables 도 위와 비슷합니다.

차이는 정수가 아닌 2진수를 넣어야죠.

 

 

 

제한 조건에는 int 대신 bin을 넣습니다.

 

 

Fixed - Charge Problem (고정비)

 

 

3가지 프로세스가 있고

1 프로세스는 고정비가 1000,

2 프로세스는 800, 3 프로세스는 900 입니다.

 

비용의 최적화는

MAX: 48x1 + 55x2 + 50x3 - 1000y1 - 800y2 -900y3 입니다.

여기서 고정비용은 나오거나 안 나오거나 이기 때문에 binary입니다.

 

이제 제약식을 계산하면

1)2x1 + 3x2+ 6x3  <= 600

2)6x1 + 3x2 + 4x3 <= 300

3)5x1 + 6x2 + 2x3 <= 400

 

하지만 이렇게만 하면 x와 y를 연결하는 고리가 없어서

무조건 값이 이상하게 나오게 됩니다.

이제 굳이 변수를 하나 만들어서 넣어 봅니다.

 

먼저 이렇게 생각해 봅시다.

엄청나게 거대한 수 M이 있다고 합시다.

이 값은 엄청 거대하기 때문에

X1<=M1Y1일 겁니다. 

단, Y가 0이면 x도 0이기 때문에 이 경우라면 = 도 가능하겠죠.

이걸 바꿔 표현하면 X1-M1Y1 <= 0 입니다.

 

그럼  x1이 확정적으로 최대가 될 수 있는 값은 멀까요?

x2 와 x3가 0인 값일 겁니다.

그러면 1), 2), 3)에서 각각 300, 50, 80이 도출됩니다.

(min 600 /2 , 300 / 6, 400 / 5)

이 중에 Min을 뽑으면 50이 되겠죠.

따라서 x1= 50만큼은 어느 경우에도 최대가 가능합니다.

즉, x1 <= 50 입니다.

 

이제 M의 값을 생각해 볼까요?

위에서 살펴본 것처럼 X는 확정적으로 최대가 될 수 있는 값이 50입니다.

이는 Y가 1이어도 마찬가지겠죠. 그럼 M의 값을 정할 수 있습니다.

(Y=0 or 1인 binary 입니다.)

그럼 X1 - 50y1 <= 0 이 됩니다.

 

이를 정리하면

Max : 48x1+55x2+50x3-1000Y1-800Y2-900Y3

제약 : 2x1 + 3x2 + 6x3 <= 600

          6x1 + 3x2 + 4x3 <= 300

          5x1 + 6x2 +2x3 <= 400

          x1 - 50y1 <= 0

          x2 - 67y2 <= 0

          x3 - 75y3 <= 0

 

이상입니다.