이진변수를 활용한 제약 모델링 개선

보조 이진변수를 도입함으로써 모델링하기 힘든 문제를 가능하게 하거나,

 

순수 / 혼합 정수계획법 문제로 바꿔줄 수 있어 유용한 경우를 살펴본다.

 

(1) 양자택일형 제약

두 가지 관계 제약식 중 반드시 하나만 성립해야 하는 조건을,

 

M(임의의 매우 큰 수)과 보조 이진변수를 도입함으로써 각각의 제약식으로 표현 가능하게 바꿔준다.

My 또는 M(1-y)가 1이 되는 경우,

 

의미 없는 제약식이 되기 때문에 사실상 해당 제약식을 제거하는 효과를 갖는다.

 

이는 M개의 제약식 중 반드시 K개만 만족시키는 조건으로 확장시켜 적용할 수 있다.

 

예시) 3개 부등식 중 반드시 2개는 만족시켜야 하는 경우 

y_1, y_2 y_3 중 하나는 1이어야 하므로, 하나의 제약식은 제거되는 효과를 가진다.

 

(2) N개의 가능한 값을 갖는 제약

예시를 통해 쉽게 이해 가능하다.

이진변수 y를 도입함으로써 왼쪽 제약식을 오른쪽처럼 표현

 

(3) 고정비용 문제

x > 0일 때 고정비용 k가 발생하지 않는다면, 이 제약식은 선형제약으로 표현 가능하다.

 

x  <=  My 제약식은, x > 0일때 y가 반드시 1이어야 한다는 의미이다.

 

 

(4) 일반 정수변수의 이진변수 표현

대부분의 변수가 이진변수이고, 일부분만 정수 변수인 경우,

 

이진정수계획법으로 문제를 바꾸기 위해 일반 정수를 이진 변수로 표현할 수 있다.

예제를 통해 쉽게 이해 가능하다.