分枝限定法とは

分枝限定法（Branch and Bound、B&B）は、数学的最適化問題、特に離散最適化や組み合わせ最適化の問題を解くためのアルゴリズムです。これらの問題では、多くの選択肢から最も良い結果をもたらす組み合わせを見つけ出す必要があります。例えば、セールスマンが複数の都市を訪れる場合、最短の経路を見つける旅行セールスマン問題（TSP）があります。このような問題は、すべての可能性を一つずつ試していくと計算量が非常に多くなるため、効率的な方法が求められます。分枝限定法は、このような問題を効率的に解くための手法の一つです。

分枝限定法の基本的な考え方

分枝限定法は、大きな問題を小さな問題に「分枝」していき、それぞれの小さな問題に対する最適な解（または部分的な解）を見つけ、「限定」することで、最終的な最適解を求めます。このプロセスは、以下のステップで構成されます。

1. 分枝（Branching）: 問題をより小さなサブ問題に分割します。これは、例えば、ある変数が取りうる値の範囲を分割することで行われます。各サブ問題は、元の問題の制約を満たす解の候補となります。
2. 評価（Evaluation）: 各サブ問題に対して、目的関数の値（最適化したい量）を評価します。これには、そのサブ問題の最適解を見つけるか、あるいはそのサブ問題に対する解の上界または下界を推定します。
3. 限定（Bounding）: 解の上界や下界を用いて、それ以上探索する必要がないサブ問題を「切り捨て」ます。たとえば、あるサブ問題の最良の可能性が既に見つかった他のサブ問題の解よりも悪い場合、そのサブ問題を探索する必要はありません。
4. 選択（Selection）: 次に探索するサブ問題を選択します。これは、最も有望なサブ問題（例えば、最も良い上界または下界を持つサブ問題）を選ぶことが多いです。
5. 繰り返し（Iteration）: 新たに選択されたサブ問題に対して、分枝、評価、限定のステップを繰り返します。

このプロセスは、最適解が見つかるか、すべてのサブ問題が探索されるまで続けられます。

分枝限定法の特徴

• 効率性: 全ての可能性を試す全列挙と比べて、分枝限定法は不必要な計算を省略するため、より効率的です。
• 汎用性: 様々な種類の最適化問題に適用可能であり、特定の問題に特化したアルゴリズムではないため、幅広い問題に対応できます。
• 正確性: 分枝限定法は最適解を保証するアルゴリズムであり、近似解ではなく正確な解を求めることができます。

分枝限定法の応用

分枝限定法は、旅行セールスマン問題のような経路問題だけでなく、スケジューリング、ネットワーク設計、資源割り当てなど、多くの実世界の問題に応用されています。また、整数計画問題など、変数が整数値を取る問題にもよく使われます。

まとめ

分枝限定法は、計算量が多くなりがちな最適化問題を効率的に解くための強力なアルゴリズムです。サブ問題に分割し、それぞれの問題に対する最適解またはその上界・下界を求め、不必要な計算を省略しながら全体の最適解を探索します。その汎用性と正確性から、様々な分野での問題解決に利用されています。