Branch and bound — 분기 한정법

분기 한정법 (영어: Branch and Bound, 약어: B&B 또는 BnB)은 이산 최적화 및 조합 최적화 문제, 특히 NP-난해 문제를 풀기 위한 정확한 알고리즘을 구성하는 일반적인 패러다임이다. 이 방법은 방향성 열거 전략으로, 허용 가능한 해의 전체 집합을 순차적으로 부분집합으로 분할(분기)하고, 각 부분집합에 대해 목적 함수 값의 추정치(한계)를 계산한다. 이러한 추정치를 통해 최적 해를 포함하지 않는 것이 명확한 부분집합을 제거(가지치기)할 수 있으며, 이는 탐색 공간을 크게 줄여 준다.

이 방법은 1960년 A. 랜드(A. Land)와 A. 도이그(A. Doig)에 의해 정수 계획법 문제를 풀기 위해 처음 제안되었다. 그 이후 이 방법은 운용과학과 컴퓨터 과학에서 가장 근본적인 접근법 중 하나가 되었다. 이 방법의 핵심 특징은 유연성으로, 구체적인 알고리즘이 아니라 풀고자 하는 문제의 구조에 적응 가능한 고수준의 전략적 체계(프레임워크)라는 점이다.

핵심 구성 요소

이 방법의 기초는 탐색 트리 형태로 구성된 해 공간의 부분집합에 적용되는 세 가지 기본 연산이다.

• 분기 (영어: Branching) — 현재의 허용 가능한 해 집합 $S_i$을 일반적으로 서로 겹치지 않는 여러 개의 더 작은 부분집합 $S_{i1},S_{i2},\dots ,S_{ik}$으로 재귀적으로 분할하는 과정이다. 각 부분집합은 새로운 하위 문제에 해당하며 탐색 트리의 자식 노드로 표현된다. 예를 들어, 정수 계획법 문제에서 분기는 LP 완화 해에서 분수 값을 갖는 변수를 기준으로 수행되는 경우가 많다.

• 한계 추정 (영어: Bounding) — 탐색 트리의 각 노드(즉, 각 하위 문제)에 대해 목적 함수 값의 추정치를 계산한다. 최소화 문제의 경우, 이는 해당 부분집합 내의 임의의 해에 대한 보장된 하한인 하한값 (lower bound)이다. 이 추정치는 대개 원래 하위 문제의 완화 — 일부 복잡한 제약(예: 정수성 제약)을 일시적으로 무시한 단순화 버전 — 를 풀어서 구한다. 가장 일반적인 방법은 LP 완화이다.

• 가지치기 (영어: Pruning) — 최적 해를 포함할 수 없는 것이 명확한 노드(및 해당 하위 트리 전체)를 탐색에서 제외하는 과정이다. 노드는 다음 중 하나의 경우에 가지치기된다:

1. 한계에 의한 가지치기: 해당 노드의 하한값이 현재까지 발견된 최선의 허용 가능한 해(현재 최적 해, incumbent)의 값보다 좋지 않은 경우(즉, 최소화 문제에서 크거나 같은 경우).
2. 허용 가능성에 의한 가지치기: 노드의 완화 해가 원래 문제에 대해 허용 가능한 경우(예: 모든 변수가 정수인 경우). 이 해를 현재 최적 해와 비교하여, 더 좋으면 최적 해를 갱신한다. 이 노드에서 추가적인 분기는 불필요하다.
3. 불가능성에 의한 가지치기: 해당 노드에 대응하는 하위 문제가 허용 가능한 해를 갖지 않는 경우.

일반 알고리즘

최소화 문제에 대한 분기 한정법의 일반화된 알고리즘은 다음 단계로 설명할 수 있다:

1. 초기화: 초기 허용 가능한 해를 구하고(예: 휴리스틱 사용), 그 값을 초기 상한값(현재 최적 해)으로 설정한다 $U$. 루트 노드(원래 문제)를 포함하는 활성 노드 큐 $Q$를 생성한다.
2. 주 반복: 큐 $Q$가 비어 있지 않은 동안:
   • 탐색 전략(예: 깊이 우선 탐색 또는 최선 우선 탐색)에 따라 $Q$에서 노드를 선택한다.
   • 해당 노드에 대한 완화를 풀어 하한값 $L$을 구한다.
   • $L\ge U$인 경우 노드를 가지치기한다.
   • 완화 해가 원래 문제에 대해 허용 가능하면 현재 최적 해를 갱신한다: $U\leftarrow L$.
   • 노드가 가지치기되지 않았고 해가 허용 가능하지 않은 경우, 분기를 수행하여 자식 노드로 분할하고 큐 $Q$에 추가한다.
3. 종료: 큐 $Q$가 비어 있으면 알고리즘이 종료된다. 현재 최적 해 $U$에 해당하는 발견된 해가 전역 최적 해이다.

핵심 성질 및 정리

• 정확성 및 수렴성: 허용 가능한 해의 집합이 유한하고 분기 절차가 수렴적(즉, 재귀적 분할 시 부분집합이 점으로 "수축"됨)이라면, 알고리즘은 유한한 단계 내에 전역 최적 해를 반드시 찾는다.
• 탐색 전략: 알고리즘의 효율성은 다음 분기 노드 선택 전략(예: 깊이 우선 탐색, 너비 우선 탐색, 최선 우선 탐색)과 분기 변수의 선택에 크게 의존한다. 현대의 솔버는 종종 하이브리드 전략을 사용한다.

예시

• 정수 계획법 문제: 이 방법의 고전적인 응용이다. 완화로는 선형 계획법을 사용한다. 분수 값을 갖는 변수 $x_j$를 기준으로 분기하여 추가 제약 조건 $x_j\le \lfloor x_j^{*}\rfloor$ 및 $x_j\ge \lceil x_j^{*}\rceil$을 갖는 두 개의 하위 문제를 생성한다.
• 외판원 문제: 해 공간은 그래프 내의 모든 가능한 해밀턴 순환이다. 분기는 간선을 기준으로(경로에 간선을 포함/제외) 수행될 수 있다. 하한값으로는 할당 문제나 최소 신장 트리 구성 등 더 단순한 문제의 해를 사용할 수 있다.

관련 개념 및 응용

• 분기 절단법 (Branch-and-Cut): B&B와 절단 평면법을 결합한 하이브리드 방법이다. 탐색 트리의 각 노드에서 완화를 푸는 것 외에도 추가 부등식(절단)을 생성하여 하한값을 강화함으로써 더 효과적인 가지치기가 가능하다.
• 백트래킹 (Backtracking): 분기 한정법은 최적화 문제를 위한 이 알고리즘의 일반화로 볼 수 있다.
• 알파-베타 가지치기: 명백히 불리한 분기를 제거하기 위해 게임 트리에서 사용되는 개념적 유사체이다.

같이 보기

• 정수 계획법
• 조합 최적화
• 외판원 문제
• NP-난해 문제
• 심플렉스법

각주

</references>