Branch and bound — 分枝限定法

分枝限定法（ぶんしげんていほう、英語: Branch and Bound、略称: B&BまたはBnB）は、離散最適化問題および組合せ最適化問題、特にNP困難な問題を解くための厳密解法を構築するための一般的なアルゴリズムパラダイムである。この手法は系統的な探索戦略であり、実行可能解の集合全体を部分集合に逐次的に分割（分枝）し、それぞれの部分集合に対して目的関数の値の評価値（限定値）を計算する。これらの評価値により、最適解を含まないと判断される部分集合を除外（剪定）することが可能となり、探索空間を大幅に削減できる。

この手法は、1960年にA. H. LandとA. G. Doigによって、整数計画問題を解くために初めて提案された。以来、オペレーションズ・リサーチおよび計算機科学において最も基本的なアプローチの一つとなっている。この手法の重要な特徴はその柔軟性にある。特定のアルゴリズムではなく、解決すべき問題の構造に適応可能な高レベルの戦略的枠組み（フレームワーク）である。

アルゴリズムの主要な構成要素

この手法は、探索木として構成される解空間の部分集合に適用される3つの基本的な操作に基づいている。

• 分枝 (英語: Branching) — 現在の実行可能解の集合 $S_i$ を、通常は互いに素な複数のより小さな部分集合 $S_{i1},S_{i2},\dots ,S_{ik}$ に再帰的に分割するプロセスである。各部分集合は新たな部分問題に対応し、探索木の子ノードとして表現される。例えば、整数計画問題では、線形計画緩和の解において非整数値をとる変数を基準に分枝を行うことが多い。

• 限定 (英語: Bounding) — 探索木の各ノード（すなわち、各部分問題）に対して、目的関数の評価値が計算される。最小化問題の場合、これは下界値（lower bound）であり、その部分集合内の任意の解に対する保証された下限値となる。多くの場合、この評価値は、元の部分問題の緩和問題（例えば、整数制約のような複雑な制約を一時的に無視した単純化された問題）を解くことによって得られる。最も一般的に用いられるのは線形計画緩和である。

• 剪定 (英語: Pruning) — 最適解を含まないことが保証されているノード（およびそれに対応する部分木全体）を探索対象から除外するプロセスである。ノードは以下のいずれかの場合に剪定される：

1. 限定値による剪定: あるノードの下界値が、現在見つかっている最良の実行可能解（暫定解、incumbent）の値よりも良くない（最小化問題の場合は大きいか等しい）場合。
2. 実行可能性による剪定: ノードの緩和問題の解が、元の問題においても実行可能である（例えば、すべての変数が整数値をとる）場合。この解は現在の暫定解と比較され、より良ければ暫定解が更新される。このノードからのさらなる分枝は不要となる。
3. 非実行可能性による剪定: ノードに対応する部分問題に実行可能解が存在しない場合。

一般的なアルゴリズム

最小化問題に対する分枝限定法の一般的なアルゴリズムは、以下のステップで記述できる：

1. 初期化: （例えばヒューリスティクスを用いて）初期実行可能解を見つけ、その値を初期の上界値（暫定解）$U$として設定する。アクティブなノードのキュー$Q$を作成し、ルートノード（元の問題）を追加する。
2. メインループ: キュー$Q$が空になるまで以下を繰り返す：
   • 探索戦略（例えば、深さ優先探索や最良優先探索）に従って$Q$からノードを一つ選択する。
   • このノードに対して緩和問題を解き、下界値$L$を得る。
   • $L\ge U$ の場合、ノードを剪定する。
   • 緩和問題の解が元の問題で実行可能な場合、暫定解を更新する: $U\leftarrow L$。
   • ノードが剪定されず、かつ解が実行可能でない場合、分枝操作を行い、子ノードに分割してそれらをキュー$Q$に追加する。
3. 終了: キュー$Q$が空になった時点でアルゴリズムは終了する。暫定解$U$に対応する解が、大域的最適解となる。

主要な特性と定理

• 正当性と収束性: 実行可能解の集合が有限であり、分枝操作が収束的（すなわち、再帰的な分割によって部分集合が点に「収縮」する）である場合、アルゴリズムは有限ステップで大域的最適解を確実に見つけ出すことが保証される。
• 探索戦略: アルゴリズムの効率は、次に分枝するノードの選択戦略（例えば、深さ優先探索、幅優先探索、最良優先探索）や、分枝変数の選択に大きく依存する。現代のソルバーは、しばしばハイブリッド戦略を用いる。

例

• 整数計画問題: この手法の古典的な応用例。緩和問題として線形計画法が用いられる。分枝は非整数値をとる変数$x_j$に対して行われ、追加制約$x_j\le \lfloor x_j^{*}\rfloor$と$x_j\ge \lceil x_j^{*}\rceil$を持つ2つの部分問題が生成される。
• 巡回セールスマン問題: 解空間はグラフ内のすべてのハミルトン閉路である。分枝は辺（経路に含めるか／含めないか）によって行われる。下界値としては、割当問題や最小全域木の構築といった、より単純な問題の解が利用されることがある。

関連概念と応用

• 分枝カット法 (Branch-and-Cut): B&Bとカット平面法を組み合わせたハイブリッド手法。探索木の各ノードで緩和問題を解くだけでなく、下界値を強化する追加の不等式（カット）を生成し、より効率的な枝の剪定を可能にする。
• バックトラッキング (Backtracking): 分枝限定法は、最適化問題に対するこのアルゴリズムの一般化と見なすことができる。
• アルファ・ベータ法: ゲーム木において、明らかに負けにつながる枝を剪定するために用いられる、概念的に類似した手法。

関連項目

• 整数計画法
• 組合せ最適化
• 巡回セールスマン問題
• NP困難な問題
• シンプレックス法

注釈

Category:Decision analysis