분기 절단법

분기 절단법 (Branch and Cut)은 조합 최적화 문제를 해결하기 위한 알고리즘 기법으로, 분기 한정법(Branch and Bound)에 절단면 방법(Cutting Plane Method)을 결합한 형태입니다. 복잡한 정수 계획법 문제를 효율적으로 해결하는 데 널리 사용됩니다.

분기 절단법의 핵심은 다음과 같습니다.

• 분기(Branching): 문제의 실행 가능한 영역을 작은 하위 문제로 나누는 과정입니다. 이 과정은 탐색 트리를 형성하며, 각 노드는 원래 문제의 제약 조건을 추가한 하위 문제를 나타냅니다. 일반적으로 정수 조건과 같이 충족되지 않은 제약 조건을 기반으로 분기가 수행됩니다.

• 한정(Bounding): 각 하위 문제에 대해 최적해의 하한(최소화 문제의 경우) 또는 상한(최대화 문제의 경우)을 계산합니다. 선형 계획 완화(Linear Programming Relaxation)와 같은 방법을 사용하여 계산된 한계는 해당 하위 문제의 최적해에 대한 정보를 제공하며, 탐색해야 할 노드를 결정하는 데 도움이 됩니다.

• 절단(Cutting): 현재 선형 계획 완화의 최적해를 실행 불가능하게 만드는 선형 부등식(절단면)을 추가합니다. 이 절단면은 정수 조건은 만족하지 않지만, 실행 가능한 정수 해는 잘라내지 않도록 설계됩니다. 절단면을 추가함으로써 선형 계획 완화의 실행 가능한 영역을 줄여 더욱 강력한 한계를 얻을 수 있습니다. 대표적인 절단면으로는 Gomory 절단면, Chvátal-Gomory 절단면, Lift-and-Project 절단면 등이 있습니다.

분기 절단법은 다음과 같은 방식으로 작동합니다.

1. 원래 문제를 선형 계획 완화하여 초기 해를 구하고, 초기 탐색 트리를 생성합니다.

2. 탐색 트리에서 아직 탐색되지 않은 노드를 선택합니다. 노드를 선택하는 전략은 깊이 우선 탐색(Depth-First Search), 넓이 우선 탐색(Breadth-First Search), 최선 우선 탐색(Best-First Search) 등 다양하게 존재합니다.

3. 선택된 노드에 해당하는 하위 문제를 선형 계획 완화하여 해를 구합니다.

4. 만약 해가 정수 조건을 만족하면, 현재까지 찾은 최적해보다 좋으면 최적해를 갱신합니다.

5. 만약 해가 정수 조건을 만족하지 않으면, 절단면을 추가하여 선형 계획 완화를 강화합니다. 추가된 절단면이 더 이상 유효하지 않으면 분기를 수행합니다.

6. 하위 문제의 한계가 현재까지 찾은 최적해보다 나쁘거나, 하위 문제가 실행 불가능한 경우, 해당 노드를 가지치기(Pruning)합니다.

7. 탐색 트리의 모든 노드가 탐색되거나 가지치기될 때까지 2-6단계를 반복합니다.

분기 절단법은 문제의 크기와 구조에 따라 효율성이 크게 달라질 수 있습니다. 특히 좋은 절단면을 찾는 것이 중요하며, 문제 특성에 맞는 절단면을 사용하는 것이 성능 향상에 도움이 됩니다.

분기 절단법은 물류, 스케줄링, 금융 등 다양한 분야에서 발생하는 조합 최적화 문제 해결에 활용되고 있습니다. 예를 들어, 차량 경로 문제(Vehicle Routing Problem), 집합 커버 문제(Set Covering Problem), 정수 계획법 기반의 포트폴리오 최적화 문제 등에 적용될 수 있습니다.