[Gurobi] big-M constraint 가 일으킬 수 있는 문제

big-M constraint 은 gurobi 를 포함한 많은 최적화 솔버에서 해의 불안정성 (instability) 문제를 일으킨다. 

우선 아래 예시를 통해 big-M constraint 가 무엇인지부터 살펴보자. y는 도로를 사용할지 말지 결정하는 binary variable 이고 10^6은 도로의 용량을 나타내며 x는 차량의 통행량이라고 해보자. 첫번째 수식을 살펴보면 y=0이면 x<=0이기 때문에 x=0이라는 것을 알 수 있다. 이는 도로가 건설되었을때만 차량이 다닐 수 있다는 사실과 연결된다. y=1 일때는 x<=10^6의 값을 가질 수 있다. 아래 수식에 명시되어있지는 않지만 y는 주로 도로를 건설하는데 필요한 매우 큰 고정 비용을 수반하며 이는 그 도로의 효용이 크지 않는한 건설하지 못하도록 막는다. 

우리가 10^-5 정확도의 실수를 다룬다고 할 때 y는 0 대신 우연히 0.000009999 의 값을 갖게될 수도 있다. 그 경우 x는 9.999 여도 첫번째 식을 만족할 수 있다. 다시말해 y가 0에 거의 근접한 값을 갖는 상황에서도 x는 양수의 값을 가질 수 있게 되며 이는 애초에 big-M constraint 를 도입한 이유 (y=1일때만 양수의 x를 가질 수 있게 하는 것)를 희석한다. 

 

따라서 이 문제를 해결하기 위해서는 big-M 값을 가능한 작게 잡는 것이 중요하다. 또한 정확도를 조정함으로써 어느정도 해결할 수 있다. 조금 더 근본적인 방법으로는 y=0 일때 x=0임을 명시적으로 드러내줄 수 있는 indicator constraint 를 적어주거나 SOS constraints 를 적어볼 수 있는데 종종 더 많은 연산시간을 필요로 한다.

 

이 포스팅은 아래 게시글의 내용을 요약하였다.

https://www.gurobi.com/documentation/9.1/refman/dealing_with_big_m_constra.html

Dealing with big-M constraints