분지절단법 (Branch and Cut Method)

한 줄 정의: 분지한정법의 탐색 과정에 정수해가 아닌 부분을 제거하는 절단평면 기법을 결합하여, 정수계획법 문제의 탐색 공간을 더욱 효율적으로 줄이는 최적화 방법입니다.

쉽게 풀면

분지한정법이 문제를 여러 조각으로 나누어 가능성 없는 부분을 통째로 버리는 방식이라면, 분지절단법은 여기에 한 가지 도구를 더 사용합니다. 바로 정수 값이 아닌 애매한 해들만 골라내어 아예 탐색 대상에서 잘라내는 절단선을 추가로 그어주는 것입니다. 이렇게 하면 나뭇가지를 치는 것 외에도 애초에 불필요한 영역을 미리 도려낼 수 있어, 같은 문제라도 더 적은 탐색으로 최적해에 도달할 수 있습니다. 대규모 정수계획법 문제를 실제로 풀 때 가장 널리 쓰이는 방법 중 하나입니다.

왜 중요한가

순수 분지한정법만으로는 대규모 문제에서 탐색해야 할 가지 수가 지나치게 많아질 수 있습니다. 분지절단법은 절단평면을 통해 완화 문제의 해가 정수해에 더 가깝게 만들어주므로 탐색 효율을 크게 높일 수 있어, 실무 규모의 정수계획법 문제를 다루는 산업공학 연구와 상용 최적화 소프트웨어에서 표준적인 해법으로 자리 잡고 있습니다.

논문에서는 이렇게 쓰입니다

"차량경로문제를 정수계획법으로 정식화하고 분지절단법을 적용하여 대규모 문제에서도 실용적인 시간 내에 최적해를 구할 수 있었다."

배송 차량의 경로를 짜는 복잡한 문제도 분지절단법을 활용해 합리적인 시간 안에 최적의 답을 찾았다는 의미입니다.

"본 연구는 절단평면 생성 규칙을 개선한 분지절단법을 제안하여 기존 분지한정법 대비 탐색 노드 수를 크게 줄였다."

절단선을 더 효과적으로 만드는 방법을 고안해, 기존 방식보다 훨씬 적은 탐색만으로 답을 찾을 수 있게 했다는 뜻입니다.

조금 더 깊게 보면

분지절단법에서 사용하는 절단평면은 정수해를 하나도 배제하지 않으면서도 완화 문제의 실수해 영역만 좁혀주는 부등식으로, 문제의 구조에 따라 다양한 형태의 절단평면이 개발되어 있습니다. 절단평면 추가와 분지 과정을 반복하면서 완화 문제의 해가 점차 정수해에 가까워지도록 유도하며, 이 과정은 대부분 상용 최적화 솔버 내부에서 자동으로 수행됩니다.

주의할 점

절단평면을 지나치게 많이 추가하면 오히려 각 단계에서 풀어야 할 완화 문제 자체가 복잡해져 전체 계산 시간이 늘어날 수 있으므로, 절단평면의 종류와 추가 시점을 적절히 조절하는 것이 중요합니다.