Branch and Bound（分枝限定法）法

分枝限定法とは、組合せ計画問題で厳密解を求めるための手法の１つです。組合せ計画問題とは、ある関数を最大化するパラメータの組の様に、パラメータの有限個の組み合わせの中から目的を満たす組を求める問題です。分枝限定法は、条件分岐を駆使して問題を部分問題にどんどん分割してきます。これを分枝操作といいます。ある部分問題において、これ以上解を探索する必要がないと判断した（部分問題を解いた）場合、部分問題の分割を止めます。これを限定操作といいます。これにより、分枝限定法は探索時間の削減を図ります。部分問題の解は暫定解と呼ばれ、各部分問題を解いた時点での最良の解と言えます。探索する必要がないと判断する条件は下記の通りです。

既に最適解が得られた
現在の暫定解よりも良い解が得られる可能性がなくなった
許容解が存在しないことがわかった（つまり実行不可能）＝　その条件分岐が不適当だということがわかった

なお部分問題を解く際、分枝限定法は問題の制約条件を緩和することで、問題を解きやすくします。緩和後の問題は緩和問題と呼ばれます。緩和問題は元の問題の条件を緩和しただけなので、緩和問題の解 $\supset$ 元々の問題の解となります。そのため緩和問題の解を求めた後に修正することで、最終的に元の問題の解を得られることができます（できることが多いそうです）。緩和の例は下記の図に記載の様に、不連続な値域→連続的な値域に変えるのが一般的なようです。