절단평면법 (Cutting-Plane Method)
한 줄 정의: 정수계획법 문제를 풀 때, 정수해를 배제하지 않으면서 실행불가능한 분수해 영역만 잘라내는 부등식(절단면)을 반복적으로 추가하여 최적 정수해에 도달하는 해법입니다.
쉽게 풀면
정수계획법 문제는 변수가 정수여야 한다는 제약 때문에 풀기가 까다롭습니다. 먼저 정수 제약을 무시하고 연속변수로 문제를 풀면(선형계획 완화) 답이 정수가 아닌 분수로 나올 수 있습니다. 절단평면법은 이렇게 나온 분수해를 제외하면서도 원래 원하는 모든 정수해는 그대로 남겨두는 새로운 부등식을 찾아 문제에 추가하고, 이 과정을 반복해 점점 정수해에 가까워지도록 만드는 방법입니다.
왜 중요한가
절단평면법은 정수계획법 문제를 완전탐색 없이도 체계적으로 좁혀 나가며 풀 수 있게 해주는 근본적인 접근법으로, 오늘날 대부분의 상용 정수계획법 solver가 사용하는 분지절단법(branch-and-cut)의 핵심 구성요소입니다.
논문에서는 이렇게 쓰입니다
"본 연구는 절단평면법(Cutting-Plane Method)을 이용하여 시설입지 문제의 선형계획 완화해에서 발생한 분수해를 제거하였다."
정수가 아닌 해를 배제하는 절단면을 추가해 문제를 정수해에 가깝게 좁혀나갔다는 의미입니다.
"고모리 절단면을 반복적으로 추가한 결과 소수의 반복만으로 정수 최적해에 도달하였다."
절단평면법의 대표적인 기법인 고모리 절단면을 사용해 비교적 빠르게 정수해를 찾았다는 뜻입니다.
조금 더 깊게 보면
절단평면법의 대표적인 방법으로 고모리(Gomory)의 절단면이 있으며, 이는 심플렉스법의 최종 표에서 정수가 아닌 기저변수의 행으로부터 유효부등식을 유도합니다. 실무에서는 절단평면법 단독보다 분지한계법(branch-and-bound)과 결합한 분지절단법(branch-and-cut) 형태로 훨씬 널리 사용됩니다.
주의할 점
고전적인 절단평면법만으로는 수렴이 매우 느리거나 절단면이 과도하게 누적되어 계산이 비효율적일 수 있어, 실무에서는 반드시 분지한계법과 병행하여 사용하는 것이 일반적입니다.