분기 한정 (Branch and Bound)

한계값으로 부분문제를 가지치기하는 정확 트리 탐색.

다른 이름: Branch and Bound · B&B · 분기-가격(확장)

해 공간을 부분문제 트리로 분할해 탐색하되, 각 노드에서 하한(현재 가지가 도달할 수 있는 최적값의 한계)을 계산해 현재 최적해(incumbent)를 이길 수 없는 가지를 통째로 잘라낸다 — 강한 하한일수록 트리가 크게 줄어든다. 2D 빈 패킹 등 절단·적재의 정확 해법의 근간이며, 열 생성과 결합하면 변수가 많은 정수 문제를 푸는 분기-가격(branch-and-price)이 된다.

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목으로 들어오는 관계 9

사용 방법
1D 절단 재고에서 분기 한정 (Branch and Bound)로
절단 재고의 정수해는 열 생성과 분기 한정을 결합한 분기-가격으로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems
  서지정보
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법
2D 빈 패킹에서 분기 한정 (Branch and Bound)로
2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 배낭 (직사각형)에서 분기 한정 (Branch and Bound)로
기하학적 2D 배낭의 정확 해법으로 분기 한정 알고리즘이 제시되었으며, 1차원 배낭 완화(직사각형 면적을 무게로)를 경계로 쓴다(Caprara & Monaci 2004).
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서On the two-dimensional Knapsack Problem
  서지정보
  Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
사용 방법
3D 빈 패킹에서 분기 한정 (Branch and Bound)로
3D 빈 패킹·컨테이너 적재의 정확 접근은 분기 한정 정식화로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Constraints in container loading – A state-of-the-art review
  서지정보
  Bortfeldt, A., Wäscher, G. (2013). Constraints in container loading – A state-of-the-art review. EJOR 229(1):1-20.
사용 방법
길로틴 절단에서 분기 한정 (Branch and Bound)로
길로틴 절단의 정확 접근은 분기 한정으로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
0/1 배낭 문제에서 분기 한정 (Branch and Bound)로
0/1 배낭 문제는 동적 계획법 외에 분기 한정으로도 정확히 풀 수 있다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
방법 공유
열 생성 (Column Generation)에서 분기 한정 (Branch and Bound)로
열 생성과 분기 한정을 결합하면 분기-가격(branch-and-price)이 되어, 정수 절단·적재 문제의 정확해에 쓰인다.
증거A · 동료심사 논문 / 공식 문서
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
- 출처 등급: A — 동료심사 논문 / 공식 문서Branch-and-Price: Column Generation for Solving Huge Integer Programs
  서지정보
  Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).
방법 공유
정수 선형 계획법 (Integer Linear Programming)에서 분기 한정 (Branch and Bound)로
정수 선형 계획 모델은 분기 한정으로 정확히 풀린다 — ILP는 문제를 기술하는 모델이고, 분기 한정은 그 모델을 푸는 해법이다.
증거A · 동료심사 논문 / 공식 문서
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
방법 공유
하한 (Lower Bounds)에서 분기 한정 (Branch and Bound)로
하한 계산은 분기 한정의 가지치기를 이끄는 핵심 구성 요소다 — 강한 하한일수록 탐색 트리를 더 많이 잘라낸다.
증거A · 동료심사 논문 / 공식 문서
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
사용 방법 1D 절단 재고에서 분기 한정 (Branch and Bound)로	절단 재고의 정수해는 열 생성과 분기 한정을 결합한 분기-가격으로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서BPPLIB: a library for bin packing and cutting stock problems 서지정보 Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
사용 방법 2D 빈 패킹에서 분기 한정 (Branch and Bound)로	2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 배낭 (직사각형)에서 분기 한정 (Branch and Bound)로	기하학적 2D 배낭의 정확 해법으로 분기 한정 알고리즘이 제시되었으며, 1차원 배낭 완화(직사각형 면적을 무게로)를 경계로 쓴다(Caprara & Monaci 2004).	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서On the two-dimensional Knapsack Problem 서지정보 Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
사용 방법 3D 빈 패킹에서 분기 한정 (Branch and Bound)로	3D 빈 패킹·컨테이너 적재의 정확 접근은 분기 한정 정식화로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Constraints in container loading – A state-of-the-art review 서지정보 Bortfeldt, A., Wäscher, G. (2013). Constraints in container loading – A state-of-the-art review. EJOR 229(1):1-20.
사용 방법 길로틴 절단에서 분기 한정 (Branch and Bound)로	길로틴 절단의 정확 접근은 분기 한정으로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 0/1 배낭 문제에서 분기 한정 (Branch and Bound)로	0/1 배낭 문제는 동적 계획법 외에 분기 한정으로도 정확히 풀 수 있다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
방법 공유 열 생성 (Column Generation)에서 분기 한정 (Branch and Bound)로	열 생성과 분기 한정을 결합하면 분기-가격(branch-and-price)이 되어, 정수 절단·적재 문제의 정확해에 쓰인다.	A · 동료심사 논문 / 공식 문서	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach. 출처 등급: A — 동료심사 논문 / 공식 문서Branch-and-Price: Column Generation for Solving Huge Integer Programs 서지정보 Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329. Formalizes combining column generation with branch-and-bound (branch-and-price).
방법 공유 정수 선형 계획법 (Integer Linear Programming)에서 분기 한정 (Branch and Bound)로	정수 선형 계획 모델은 분기 한정으로 정확히 풀린다 — ILP는 문제를 기술하는 모델이고, 분기 한정은 그 모델을 푸는 해법이다.	A · 동료심사 논문 / 공식 문서	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
방법 공유 하한 (Lower Bounds)에서 분기 한정 (Branch and Bound)로	하한 계산은 분기 한정의 가지치기를 이끄는 핵심 구성 요소다 — 강한 하한일수록 탐색 트리를 더 많이 잘라낸다.	A · 동료심사 논문 / 공식 문서	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.