고모리 절단 (Gomory Cut)
한 줄 정의: 단체표의 분수해 행에서 소수부를 이용해 만드는 정수계획용 절단 부등식입니다.
쉽게 풀면
정수계획 문제에서 정수 조건을 빼고 풀면 답이 2.5처럼 분수로 나올 수 있습니다. 고모리 절단은 이 분수해를 잘라 내되 정수해는 하나도 잃지 않는 새 제약을 단체표에서 기계적으로 만들어 줍니다. 이 제약을 추가하고 다시 풀기를 반복하면 정수해에 다가갑니다.
왜 중요한가
절단평면법의 원조이자 현대 혼합정수계획 솔버에서 여전히 중요한 절단입니다. 분지절단법의 성능을 다루는 논문에서 GMI 절단이라는 이름으로 자주 등장합니다.
논문에서는 이렇게 쓰입니다
"루트 노드에서 GMI 절단을 3라운드 추가한 결과, LP 완화의 최적성 간격이 18.4%에서 6.1%로 줄어들었다."
절단의 효과를 간격(gap) 감소로 보고한 예입니다.
조금 더 깊게 보면
Gomory(1958)는 순수 정수계획에서 LP 최적 단체표의 한 행 x_i + Σ a_j x_j = b를 골라, 각 계수의 소수부 f(·)로 Σ f(a_j) x_j ≥ f(b)라는 부등식을 만들었습니다. 현재 분수해에서는 비기저변수가 모두 0이라 이 부등식을 어기므로 해가 잘려 나가지만, 모든 정수 가능해는 이를 만족합니다. 행 선택 규칙 등을 적절히 정하면 유한 번 안에 끝난다는 수렴성이 증명되어 있습니다. 혼합정수문제로 확장한 형태를 GMI(Gomory Mixed-Integer) 절단이라고 합니다. 단독으로는 수치 오차와 느린 수렴 문제가 있어 오늘날에는 분지한정법과 결합해 사용합니다.
주의할 점
'절단평면법'이 유효부등식을 추가해 나가는 일반 틀이라면, 고모리 절단은 단체표에서 자동 생성되는 특정 절단입니다. 문제 구조를 활용하는 절단(예: 커버 부등식)과 혼동하지 않아야 합니다.