Branch and Bound

分枝限定法は分岐で解空間を探索し、限界値を用いて最適解を含まない部分木を枝刈りする。離散最適化に使われる。

目的

組合せ最適化問題を厳密に解き、枝刈りによる探索の高速化を図る。

大域的な最良限界値を維持する。分岐では問題を部分問題へ分割する。限定では各部分問題の下界または上界を計算し、現時点の最良値を上回らない限り枝刈りする。整数計画や TSP でよく使われる。