분지한정법

최적설계 수치해석 마지막 수정: 2026-08-03 04:12:07

1. 개요[편집]

다 세어보긴 해야 하는데, 다 세어보면 죽는다. 그래서 안 세어도 되는 걸 증명하고 버린다.

분지한정법(分枝限定法, Branch and Bound, B&B)은 이산 최적화 문제의 해공간을 재귀적으로 부분집합으로 쪼개고(분지), 각 부분집합이 담을 수 있는 최선의 목적함수 값을 완화 문제로 계산한 뒤(한정), 그 경계가 이미 확보한 해보다 나쁘면 부분집합 전체를 탐색 없이 버리는(가지치기) 완전 탐색 알고리즘이다. “완전 탐색”이라는 말이 중요하다 — B&B는 근사 알고리즘이나 유전 알고리즘 같은 휴리스틱과 달리, 끝까지 돌리면 전역 최적해임을 증명한 해를 내놓는다.

1960년 랜드(A. H. Land)와 도이그(A. G. Doig)가 정수계획법을 풀려고 고안했고, “branch and bound”라는 이름 자체는 1963년 리틀(J. D. C. Little) 등이 외판원 문제에 적용하면서 붙었다.¹ 오늘날 모든 상용 MIP 솔버(CPLEX, Gurobi, SCIP, HiGHS)의 심장이 이것이며, 배낭 문제·스케줄링·조합 최적화 전반, 나아가 게임 트리의 알파-베타 가지치기(미니맥스 알고리즘)까지 같은 사상을 공유한다.

2. 세 개의 부품[편집]

최소화 문제 $\min\{c^\top x : x \in S\}$ 를 기준으로 설명한다.

**분지(branching)**는 실행가능 집합을 $S = S_1 \cup S_2 \cup \dots \cup S_k$ 로 쪼개는 규칙이다. 정수변수 $x_j$ 의 완화 해가 $x_j^* = 3.4$ 처럼 분수로 나오면 $x_j \le 3$ 인 자식과 $x_j \ge 4$ 인 자식으로 나누는 것이 가장 흔한 이분 분지다. 이 두 자식의 합집합은 원래의 정수 실행가능 집합을 하나도 잃지 않으면서, 현재의 분수해 $x^*$ 만은 양쪽 모두에서 배제한다. 이 “잃지 않으면서 현재 해를 죽인다”는 성질이 없으면 B&B는 종료를 보장하지 못한다.

**한정(bounding)**은 각 부분문제에서 완화(relaxation) 문제를 풀어 하한 $\underline{z}(S_i) \le \min\{c^\top x : x \in S_i\}$ 를 얻는 단계다. 정수 조건을 버리고 선형계획법으로 푸는 LP 완화가 표준이다.

가지치기(pruning/fathoming) 는 세 가지 사유로 일어난다.

사유	조건	의미
실행불가	완화 문제가 infeasible	이 가지엔 해가 아예 없다
한계	$\underline{z}(S_i) \ge z^{\text{inc}}$	여길 다 뒤져도 지금보다 나을 수 없다
최적성	완화 해가 이미 정수	이 가지의 최적해를 찾았다, 더 쪼갤 필요 없음

여기서 $z^{\text{inc}}$ 는 인커번트(incumbent), 즉 지금까지 찾은 최선의 실행가능 해의 값이다. 인커번트는 상한, 완화 경계는 하한이므로 둘 사이의 거리가 곧 “얼마나 모르는지”의 정량이다.

3. 완화의 강도가 전부다[편집]

B&B의 성능을 결정하는 것은 분지 규칙도, 자료구조도 아니고 경계가 얼마나 타이트한가다. 경계가 느슨하면 가지치기가 안 되고, 가지치기가 안 되면 트리는 $2^n$ 으로 자란다. 알고리즘 골격은 30분이면 짜지만 실용적인 솔버가 되기까지 60년이 걸린 이유가 이것이다.

LP 완화가 표준인 이유는 싸고(심플렉스 warm start로 자식 노드는 몇 십 회 피벗이면 재최적화된다) 자동이기 때문이다. 여기에 절단평면법으로 유효 부등식을 얹으면 완화 다면체가 정수 볼록포에 더 가까워지면서 경계가 올라간다.

또 하나의 축이 라그랑주 완화다. 어려운 제약 $Ax \le b$ 를 라그랑주 승수법의 방식으로 목적함수에 벌점으로 흡수시키면

L(\lambda) = \min_{x \in Q} \; c^\top x + \lambda^\top (Ax - b), \qquad \lambda \ge 0

이 되고, 임의의 $\lambda \ge 0$ 에 대해 $L(\lambda)$ 는 항상 하한이다. 이걸 $\lambda$ 에 대해 최대화한 라그랑주 쌍대 경계는 남은 집합 $Q$ 가 정수성 성질(integrality property)을 갖지 않을 때 LP 완화보다 엄밀히 강하다.² 반대로 $Q$ 의 LP 완화가 자동으로 정수해를 주는 구조(네트워크 흐름 같은)면 라그랑주 경계는 LP 경계와 정확히 같아지고, 고생만 하고 얻는 게 없다.

4. 탐색 전략 — 메모리와 경계의 줄다리기[편집]

살아 있는 노드를 어떤 순서로 꺼내느냐가 두 번째 설계 결정이다.

깊이 우선(DFS): 스택 하나면 되고 메모리가 트리 깊이에 비례한다. 부모의 LP 기저를 그대로 물려받아 재최적화가 빠르고, 실행가능 해(=인커번트)를 일찍 만나 상한을 확보한다. 대신 나쁜 서브트리에 박히면 한참을 헤맨다.
최상 우선/최적 경계 우선(best-bound): 하한이 가장 작은 노드를 먼저 연다. 이론상 탐색 노드 수가 최소이고 전역 하한이 빠르게 올라가지만, 살아 있는 노드를 전부 우선순위 큐에 들고 있어야 해서 메모리가 터진다. 인커번트를 늦게 만나 초반 가지치기가 안 되는 것도 문제.
실무 하이브리드: 초반엔 DFS로 잠수(diving)해서 인커번트를 확보하고, 이후 best-bound로 갈아타 갭을 닫는다. 상용 솔버가 하는 짓이 대체로 이것이다.

최적성 갭은 보고서에 찍히는 그 숫자다. 최소화 기준으로

\text{gap} = \frac{z^{\text{inc}} - z^{\text{LB}}}{|z^{\text{inc}}|}

이며, 솔버 기본 종료 조건은 대체로 상대 갭 $10^{-4}$ 다.³ 산업 현장에서 “최적해를 찾았다”는 말의 실제 의미는 대개 “갭 1% 이하에서 시간이 다 됐다”이다. 그래도 이건 담금질 모사나 타부 서치가 절대 줄 수 없는 정보 — 최악의 경우에도 이만큼 이내라는 보증서다.

5. 분지 규칙[편집]

어느 분수 변수를 쪼갤지 고르는 문제는 생각보다 훨씬 중요하다. 트리 크기가 규칙에 따라 수십 배 차이난다.

가장 분수적인 변수(most fractional): $|x_j^* - 0.5|$ 가 최소인 변수를 고른다. 직관적이지만, 실증 연구에서 무작위 선택보다 나을 것이 없다는 결론이 나온 유명한 규칙이다.⁴
강분지(strong branching): 후보 변수마다 두 자식의 LP를 실제로 (몇 회 피벗만) 풀어보고 경계 개선량이 가장 큰 변수를 고른다. 트리는 확실히 작아지지만 노드당 비용이 폭발한다.
의사비용(pseudocost): 과거에 그 변수를 쪼갰을 때 단위 분수 이동당 경계가 얼마나 올랐는지를 누적 통계로 들고 있다가 예측에 쓴다. 공짜에 가깝지만 초반엔 통계가 없다.
신뢰도 분지(reliability branching): 통계가 부족한 변수만 강분지로 초기화하고 나머지는 의사비용으로 처리하는 절충안. 현대 솔버의 기본값.

6. 확장 — 절단과 가격[편집]

분지절단(branch-and-cut): 각 노드에서 절단평면법을 돌려 완화를 조인 뒤 분지한다. 1991년 파드베르크와 리날디가 이 조합으로 수천 도시급 외판원 문제를 최적해까지 밀어붙이면서 표준이 됐다. 오늘날 “MIP 솔버”는 사실상 branch-and-cut의 다른 이름이다.
분지가격(branch-and-price): 변수가 지수 개인 정식화(경로 하나가 변수 하나인 승무원 스케줄링 등)를 열 생성으로 다룬다. 각 노드의 LP를 열 생성으로 풀고, 분지 규칙은 생성된 열 구조를 깨지 않도록 원래 문제 공간에서 설계해야 한다. 둘 다 쓰면 branch-cut-and-price. 제약이 아니라 변수를 분리해 마스터-부문제로 나누는 벤더스 분해와 짝을 이루는 쌍둥이 기법이기도 하다.
비볼록 연속 문제로 넘어가면 구간 산술과 볼록 하계포락(McCormick 완화)을 경계로 쓰는 공간 분지한정(spatial B&B)이 되고, 이것이 전역 최적설계용 비선형 솔버(BARON, SCIP, Couenne)의 골격이다. 볼록 최적화가 아닌 문제를 그래도 전역으로 풀겠다는 마지막 보루.

7. 여담[편집]

동적 계획법과 자주 비교되는데, DP는 상태를 병합해 중복 계산을 없애고 B&B는 경계로 영역을 통째로 버린다. 배낭류에서는 DP 기반 경계를 B&B의 한정 단계에 꽂아 넣는 하이브리드가 흔하다.
노드 수는 이론적으로 여전히 지수적이다. B&B가 빠른 것이 아니라, 현실 문제의 LP 완화가 의외로 좋아서 빠른 것이다. 완화가 약한 정식화를 들고 오면 솔버는 정직하게 지수 시간을 소비한다.
그래서 실무 조언 1순위는 언제나 “알고리즘 튜닝하지 말고 정식화를 바꿔라”다. big-M 상수를 1e9로 박아 두고 왜 안 풀리냐고 묻는 것은 국룰 실수다.

8. 관련 문서[편집]

Land, A. H. & Doig, A. G. (1960). “An Automatic Method of Solving Discrete Programming Problems”, Econometrica 28(3). 정작 이 논문에는 branch and bound라는 표현이 없다. 이름을 붙인 건 3년 뒤 외판원 문제를 푼 사람들이고, 학계에서 이름을 잘 지으면 인용이 따라온다는 교훈의 교과서적 사례다. ↩
Geoffrion, A. M. (1974). 라그랑주 완화가 LP 완화와 같아지는 조건이 바로 “남은 부분문제의 LP 완화가 항상 정수 꼭짓점 해를 준다”는 정수성 성질이다. 즉 남긴 부분이 너무 쉬우면 경계도 딱 그만큼만 좋다. 세상에 공짜 점심은 없다. ↩
Gurobi·CPLEX의 MIPGap 기본값이 1e-4. 즉 기본 설정으로 “Optimal”이라 찍힌 결과도 엄밀히는 0.01% 이내의 준최적해다. 논문에 최적해라고 쓰기 전에 갭 설정을 한 번 확인해 보자. ↩
Achterberg, T., Koch, T. & Martin, A. (2005). “Branching rules revisited”, Operations Research Letters 33(1). most-infeasible branching이 무작위 분지 대비 유의미한 개선을 주지 못한다는 실험 결과가 여기 있다. 20년 넘게 교과서에 실려 온 직관 하나가 이렇게 정리됐다. ↩