---
title: "Branch and bound — 분기 한정법"
source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95"
wiki: "systems-analysis.info/int"
article: "Branch_and_bound_—_분기_한정법"
language: "ko"
categories:
- "Category:Korean"
- "Category:Operations research"
revision_id: 821
wiki_created_at: 2026-09-06T22:39:19Z
wiki_modified_at: 2026-09-06T22:39:19Z
downloaded_at: 2026-09-07T22:42:33Z
---
# Branch and bound — 분기 한정법
**분기 한정법** (영어: *Branch and Bound*, 약어: **B&B** 또는 **BnB**)은 이산 최적화 및 조합 최적화 문제, 특히 NP-난해 문제를 풀기 위한 정확한 알고리즘을 구성하는 일반적인 패러다임이다[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-en-wiki-bnb-1). 이 방법은 방향성 열거 전략으로, 허용 가능한 해의 전체 집합을 순차적으로 부분집합으로 분할(**분기**)하고, 각 부분집합에 대해 목적 함수 값의 추정치(**한계**)를 계산한다. 이러한 추정치를 통해 최적 해를 포함하지 않는 것이 명확한 부분집합을 제거(가지치기)할 수 있으며, 이는 탐색 공간을 크게 줄여 준다[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-ru-wiki-bnb-2).
이 방법은 1960년 A. 랜드(A. Land)와 A. 도이그(A. Doig)에 의해 정수 계획법 문제를 풀기 위해 처음 제안되었다[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-land-doig-1960-3). 그 이후 이 방법은 운용과학과 컴퓨터 과학에서 가장 근본적인 접근법 중 하나가 되었다. 이 방법의 핵심 특징은 유연성으로, 구체적인 알고리즘이 아니라 풀고자 하는 문제의 구조에 적응 가능한 고수준의 전략적 체계(프레임워크)라는 점이다.
## 핵심 구성 요소
이 방법의 기초는 탐색 트리 형태로 구성된 해 공간의 부분집합에 적용되는 세 가지 기본 연산이다.
- **분기** (영어: *Branching*) — 현재의 허용 가능한 해 집합 $S_{i}$을 일반적으로 서로 겹치지 않는 여러 개의 더 작은 부분집합 $S_{i1},S_{i2},\ldots,S_{ik}$으로 재귀적으로 분할하는 과정이다. 각 부분집합은 새로운 하위 문제에 해당하며 탐색 트리의 자식 노드로 표현된다. 예를 들어, 정수 계획법 문제에서 분기는 LP 완화 해에서 분수 값을 갖는 변수를 기준으로 수행되는 경우가 많다.
- **한계 추정** (영어: *Bounding*) — 탐색 트리의 각 노드(즉, 각 하위 문제)에 대해 목적 함수 값의 추정치를 계산한다. 최소화 문제의 경우, 이는 해당 부분집합 내의 임의의 해에 대한 보장된 하한인 **하한값** (*lower bound*)이다. 이 추정치는 대개 원래 하위 문제의 *완화* — 일부 복잡한 제약(예: 정수성 제약)을 일시적으로 무시한 단순화 버전 — 를 풀어서 구한다. 가장 일반적인 방법은 LP 완화이다.
- **가지치기** (영어: *Pruning*) — 최적 해를 포함할 수 없는 것이 명확한 노드(및 해당 하위 트리 전체)를 탐색에서 제외하는 과정이다. 노드는 다음 중 하나의 경우에 가지치기된다:
1. **한계에 의한 가지치기**: 해당 노드의 하한값이 현재까지 발견된 최선의 허용 가능한 해(**현재 최적 해**, *incumbent*)의 값보다 좋지 않은 경우(즉, 최소화 문제에서 크거나 같은 경우).
2. **허용 가능성에 의한 가지치기**: 노드의 완화 해가 원래 문제에 대해 허용 가능한 경우(예: 모든 변수가 정수인 경우). 이 해를 현재 최적 해와 비교하여, 더 좋으면 최적 해를 갱신한다. 이 노드에서 추가적인 분기는 불필요하다.
3. **불가능성에 의한 가지치기**: 해당 노드에 대응하는 하위 문제가 허용 가능한 해를 갖지 않는 경우.
## 일반 알고리즘
최소화 문제에 대한 분기 한정법의 일반화된 알고리즘은 다음 단계로 설명할 수 있다:
1. **초기화:** 초기 허용 가능한 해를 구하고(예: 휴리스틱 사용), 그 값을 초기 상한값(현재 최적 해)으로 설정한다 $U$. 루트 노드(원래 문제)를 포함하는 활성 노드 큐 $Q$를 생성한다.
2. **주 반복:** 큐 $Q$가 비어 있지 않은 동안:
- 탐색 전략(예: 깊이 우선 탐색 또는 최선 우선 탐색)에 따라 $Q$에서 노드를 선택한다.
- 해당 노드에 대한 완화를 풀어 하한값 $L$을 구한다.
- $L \geq U$인 경우 노드를 **가지치기**한다.
- 완화 해가 원래 문제에 대해 허용 가능하면 현재 최적 해를 갱신한다: $U\leftarrow L$.
- 노드가 가지치기되지 않았고 해가 허용 가능하지 않은 경우, **분기**를 수행하여 자식 노드로 분할하고 큐 $Q$에 추가한다.
3. **종료:** 큐 $Q$가 비어 있으면 알고리즘이 종료된다. 현재 최적 해 $U$에 해당하는 발견된 해가 전역 최적 해이다.
## 핵심 성질 및 정리
- **정확성 및 수렴성:** 허용 가능한 해의 집합이 유한하고 분기 절차가 수렴적(즉, 재귀적 분할 시 부분집합이 점으로 "수축"됨)이라면, 알고리즘은 유한한 단계 내에 전역 최적 해를 반드시 찾는다[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-conitzer-duke-4).
- **탐색 전략:** 알고리즘의 효율성은 다음 분기 노드 선택 전략(예: 깊이 우선 탐색, 너비 우선 탐색, 최선 우선 탐색)과 분기 변수의 선택에 크게 의존한다. 현대의 솔버는 종종 하이브리드 전략을 사용한다[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-maudet-danoy-2024-5).
## 예시
- **정수 계획법 문제**: 이 방법의 고전적인 응용이다. 완화로는 선형 계획법을 사용한다. 분수 값을 갖는 변수 $x_{j}$를 기준으로 분기하여 추가 제약 조건 $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ 및 $x_{j} \geq \lceil x_{j}^{\ast}\rceil$을 갖는 두 개의 하위 문제를 생성한다.
- **외판원 문제**: 해 공간은 그래프 내의 모든 가능한 해밀턴 순환이다. 분기는 간선을 기준으로(경로에 간선을 포함/제외) 수행될 수 있다. 하한값으로는 할당 문제나 최소 신장 트리 구성 등 더 단순한 문제의 해를 사용할 수 있다[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-little-1963-6).
## 관련 개념 및 응용
- **분기 절단법** (*Branch-and-Cut*): B&B와 절단 평면법을 결합한 하이브리드 방법이다. 탐색 트리의 각 노드에서 완화를 푸는 것 외에도 추가 부등식(절단)을 생성하여 하한값을 강화함으로써 더 효과적인 가지치기가 가능하다.
- **백트래킹** (*Backtracking*): 분기 한정법은 최적화 문제를 위한 이 알고리즘의 일반화로 볼 수 있다.
- **알파-베타 가지치기**: 명백히 불리한 분기를 제거하기 위해 게임 트리에서 사용되는 개념적 유사체이다.
## 같이 보기
- 정수 계획법
- 조합 최적화
- 외판원 문제
- NP-난해 문제
- 심플렉스법
## 각주
[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-en-wiki-bnb-1) [\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-ru-wiki-bnb-2) [\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-land-doig-1960-3) [\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-conitzer-duke-4) [\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-maudet-danoy-2024-5) [\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_note-little-1963-6) \
1. ↑ [1.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-en-wiki-bnb_1-0) [1.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-en-wiki-bnb_1-1) Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
2. ↑ [2.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-ru-wiki-bnb_2-0) [2.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-ru-wiki-bnb_2-1) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
3. ↑ [3.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-land-doig-1960_3-0) [3.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-land-doig-1960_3-1) Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. *Econometrica*, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
4. ↑ [4.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-conitzer-duke_4-0) [4.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-conitzer-duke_4-1) Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
5. ↑ [5.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-maudet-danoy-2024_5-0) [5.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-maudet-danoy-2024_5-1) Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. *arXiv preprint arXiv:2412.09444*. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
6. ↑ [6.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-little-1963_6-0) [6.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%EB%B6%84%EA%B8%B0_%ED%95%9C%EC%A0%95%EB%B2%95#cite_ref-little-1963_6-1) 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. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf