분기 한정 (Branch and Bound)

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