분지한정법 (Branch and Bound Method)
쉽게 풀면
모든 경우의 수를 하나하나 다 확인하려면 시간이 너무 오래 걸리는 문제가 있습니다. 분지한정법은 이런 문제를 풀 때, 전체 경우의 수를 몇 개의 그룹으로 나눈 다음 각 그룹에서 얻을 수 있는 최선의 결과가 어느 정도인지를 먼저 가늠해봅니다. 만약 어떤 그룹에서 아무리 잘해도 지금까지 찾은 최선의 답보다 못하다는 것이 확인되면, 그 그룹은 더 이상 살펴볼 필요 없이 통째로 포기합니다. 이렇게 가능성 없는 경우들을 미리 걸러내면서 탐색 범위를 좁혀나가면, 모든 경우를 다 확인하지 않고도 최적해를 찾을 수 있습니다.
왜 중요한가
생산 계획, 시설 입지 선정, 일정 계획처럼 변수가 정수 값만 가질 수 있는 정수계획법 문제는 모든 경우를 다 따지면 계산량이 폭발적으로 늘어납니다. 분지한정법은 이런 문제에서 탐색 범위를 체계적으로 줄여 실용적인 시간 안에 최적해 또는 최적에 가까운 해를 찾을 수 있게 해주기 때문에 산업공학의 최적화 논문에서 핵심적인 해법으로 다뤄집니다.
어떤 절차인가
분지한정법은 해 공간을 쪼개고(분지, branch), 쪼갠 부분마다 얻을 수 있는 값의 한계를 계산해(한정, bound) 더 볼 필요가 없는 부분을 버리는(가지치기, prune) 일을 되풀이합니다. 최소화 문제를 기준으로 하면 이렇습니다.
- 휴리스틱으로 해 하나를 찾아 그 값 B를 현재까지의 최선(상한)으로 둡니다. 없으면 B를 무한대로 둡니다.
- 탐색 후보 목록에서 부분 문제 하나를 꺼내 하한을 계산합니다. 하한이 B 이상이면 이 부분에서는 B보다 좋은 해가 나올 수 없으므로 버립니다.
- 그렇지 않으면 부분 문제를 더 작은 부분 문제들로 나누어 목록에 넣습니다. 쪼갠 끝에 해 하나가 완성되면 값을 B와 비교해 더 좋으면 B를 갱신합니다.
- 목록이 비면 B가 최적값입니다.
한계를 구하는 방법이 없으면 이 방법은 모든 후보를 다 살피는 완전 탐색과 다르지 않습니다. 정수계획법에서는 정수 조건을 잠시 없앤 선형계획 완화 문제를 풀어 한계를 얻는 방식이 흔합니다. 이 방법은 1960년 영국 런던정경대(LSE)에서 랜드(Ailsa Land)와 도이그(Alison Doig)가 이산 계획 문제용으로 처음 제안한 것으로 정리됩니다.
언제 쓰고 무엇을 얻나
NP-난해(NP-hard)한 최적화 문제를 푸는 데 가장 널리 쓰이는 도구로 소개됩니다. 얻는 것은 근사해가 아니라 최적성이 증명된 해이고, 도중에 멈추면 상한과 하한의 격차(gap)로 현재 해가 얼마나 최적에 가까운지 알 수 있습니다. 탐색 순서는 후보 목록을 스택으로 쓰면 깊이 우선, 하한이 작은 순서로 꺼내면 최선 우선이 됩니다.
가상의 예 배낭 문제(가치를 최대화): 물건 네 개의 가치 60, 100, 120, 80, 무게 10, 20, 30, 25, 배낭 용량 50. 가치/무게 비가 큰 순서(6, 5, 4, 3.2)로 정렬해 쪼개고, 남은 물건을 쪼갤 수 있다고 허용한 선형 완화로 상한을 구했습니다(코드로 실행).
| 단계 | 결과 |
|---|---|
| 뿌리 마디의 상한 | 60 + 100 + 120의 2/3 = 240 (물건 3을 20/30만큼 담는 완화) |
| 처음 찾은 정수해 | 물건 1+2 = 가치 160, 이어서 물건 1+3 = 180 |
| 최적해 | 물건 2+3 = 가치 220 (무게 50) |
| 방문한 마디 수 | 15개 (가능한 전체 31개 중). 그중 3곳은 상한이 현재 최선 이하여서 가지치기됨 |
작은 예라 절약이 크지 않지만, 품목이 늘면 가지치기되는 가지의 크기가 기하급수적으로 커져 효과도 커집니다.
논문에는 이렇게 적는다
- 문제를 정수계획으로 어떻게 정식화했는지와, 한계를 어떤 완화(선형계획 완화 등)로 구했는지를 적습니다.
- 분지 규칙(어느 변수를 먼저 쪼개는가)과 탐색 순서(깊이 우선/최선 우선)를 적습니다. 같은 문제도 이 선택에 따라 계산 시간이 크게 달라질 수 있습니다.
- 초기 상한을 어떤 휴리스틱으로 정했는지, 시간 제한과 허용 격차(gap)를 얼마로 두었는지, 사용한 해결기와 버전을 적습니다.
- 최적해를 증명했는지, 시간 제한에서 멈춘 현재 최선해인지를 구분해서 보고합니다.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
여러 후보지 중 어디에 시설을 설치해야 하는지를 정수계획 문제로 만들고, 탐색 범위를 좁혀가며 최적의 조합을 찾았다는 의미입니다.
변수가 많은 복잡한 일정 계획 문제도 분지한정법을 통해 실용적인 시간 안에 풀 수 있었다는 뜻입니다.
조금 더 깊게 보면
분지한정법은 해공간을 나누는 분지 단계와, 각 부분 문제의 완화된 형태를 풀어 상한 또는 하한 값을 구하는 한정 단계를 반복하는 구조로 이루어집니다. 이때 정수 제약을 잠시 무시하고 연속 변수로 완화한 문제를 먼저 풀어 한계값을 구하는 방식이 흔히 쓰이며, 이 한계값이 지금까지 찾은 최선의 해보다 나쁘면 해당 가지는 더 탐색하지 않고 가지치기합니다.
주의할 점
문제 규모가 매우 크거나 완화 문제의 한계값이 실제 최적값과 차이가 크면 가지치기 효과가 떨어져 탐색 시간이 크게 늘어날 수 있습니다. 따라서 실무에서는 분지 순서나 완화 방식을 문제 특성에 맞게 조정하는 것이 중요합니다.
헷갈리기 쉬운 용어
| 용어 | 한 줄 설명 | 분지한정법과의 관계 |
|---|---|---|
| 분지절단법 | 분지한정 안에서 절단평면으로 선형 완화를 조여 가는 방법 | 분지한정법의 확장 |
| 분지가격법 | 분지한정법과 열생성을 결합한, 변수가 매우 많은 문제용 방법 | 분지한정법의 확장 |
| 라그랑지 완화 | 어려운 제약을 비용으로 바꿔 쉬운 문제로 근사하는 완화 방법 | 분지한정의 한계 계산에 쓰일 수 있는 완화 방법 |
| 동적계획법 | 부분 문제의 답을 저장해 겹치는 계산을 줄이는 방법 | 분지한정법과는 다른 계열의 해법 |
참고 문헌
- Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497.
- Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. (1963). An algorithm for the traveling salesman problem. Operations Research, 11(6), 972–989.
- Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79–102.
- Wolsey, L. A. (1998). Integer Programming. Wiley.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.