분기 한정법 (branch and bound)

한 줄 정의: 탐색 공간을 여러 부분 문제(분기)로 나누고, 각 부분 문제의 해가 도달할 수 있는 값의 상한 또는 하한(한계)을 계산하여 최적해를 포함할 수 없는 가지를 미리 제거하는 최적화 탐색 기법.

쉽게 풀면

분기 한정법은 백트래킹과 비슷하지만, 단순히 유효성만 확인하는 것이 아니라 '이 가지를 계속 탐색해봤자 지금까지 찾은 최선의 답보다 나을 수 없다'는 것을 수학적으로 계산해 미리 잘라낸다. 예를 들어 배낭 문제를 풀 때, 어떤 선택 경로가 이론적으로 도달할 수 있는 최대 가치가 이미 찾은 답보다 낮다면 그 경로는 더 볼 필요가 없다. 이를 통해 완전 탐색보다 훨씬 적은 경우의 수만 살펴보고도 최적해를 찾을 수 있다.

왜 중요한가

분기 한정법은 정수계획법, 조합 최적화, 스케줄링, 회로 설계 자동화 등 '정확한 최적해'가 필요한 분야에서 완전 탐색의 대안으로 자주 다뤄진다. 휴리스틱이나 근사 알고리즘과 달리 최적성을 보장하면서도 실용적인 시간 안에 답을 구할 수 있어, 운영과학·정수계획법 솔버(예: 상용 MIP 솔버)의 핵심 알고리즘으로 쓰인다. 또한 한계 함수를 어떻게 설계하느냐에 따라 성능 차이가 크게 나기 때문에, 새로운 문제 영역에 맞춘 한계 함수 설계 자체가 하나의 연구 주제가 된다.

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

"본 연구는 분기 한정법을 적용하여 각 노드에서 선형 완화 문제의 해를 상한으로 사용함으로써 탐색 트리의 크기를 대폭 줄였다."

정수계획법이나 조합 최적화 문제를 정확히 풀되 탐색 효율을 높이는 기법을 설명할 때 사용된다.

"차량 경로 문제에서 분기 한정법과 열 생성(column generation) 기법을 결합하여 대규모 인스턴스에서도 엄밀한 최적해를 도출하였다."

운영과학·물류 최적화 분야에서 분기 한정법이 다른 정확 해법 기법과 결합되어 확장성을 높이는 방식으로 쓰이는 예다.

"제안된 회로 설계 자동화 도구는 분기 한정법 기반 탐색을 사용하여 설계 공간을 가지치기하고, 제약 조건을 위반하는 하위 트리를 조기에 배제하였다."

하드웨어·설계 자동화 분야에서 제약 만족 문제를 정확히 풀기 위해 분기 한정법을 사용하는 사례를 보여준다.

조금 더 깊게 보면

논문에서 분기 한정법을 다룰 때는 한계(bound)를 어떻게 계산하는지가 핵심 논점이 되는 경우가 많다. 대표적으로 정수계획법에서는 정수 제약을 잠시 풀어준 선형 완화(LP relaxation) 문제의 해를 상한으로 쓰는 방식이 널리 쓰이며, 이 완화 문제를 얼마나 타이트하게(느슨하지 않게) 설계하느냐가 탐색 효율을 좌우한다. 또한 분기 순서(어떤 변수를 먼저 나눌지), 탐색 전략(깊이 우선, 최선 우선 등), 그리고 열 생성이나 절단평면법(cutting plane) 같은 보조 기법과의 결합 여부도 논문에서 자주 비교되는 요소다. 성능은 대개 탐색한 노드 수, 실행 시간, 최적성 격차(optimality gap) 등의 지표로 보고된다.

주의할 점

한계값(bound)을 계산하는 방법이 느슨하면 가지치기 효과가 떨어져 사실상 완전 탐색과 다를 바 없어질 수 있으므로, 한계 함수의 품질이 성능을 좌우한다.