Branch and Bound（ブランチ・アンド・バウンド法）

Branch and Bound（ブランチ・アンド・バウンド法）は、1960年にAilsa LandとAlison Doigによって導入された、組み合わせ最適化問題および整数最適化問題のための系統的かつ厳密なアルゴリズムである。これは、探索空間を部分問題の木として組織化し、緩和問題から導出される上界を用いて、既知の最良解を改善できない枝を刈り込み、大域的最適整数解を見つけることを保証する。これは、オペレーションズ・リサーチ、ロジスティクス、スケジューリング、工学設計で使用される現代の混合整数計画法のソルバーの基盤となっている。