分枝限定法

分枝限定法（ぶんしげんていほう、英: branch and bound, BB）は、各種最適化問題（特に離散最適化と組合せ最適化）の最適解を求める汎用アルゴリズムである。分枝操作（英: branching operation）と限定操作（英: bounding operation）から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。

1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。

概要

関数 ${\displaystyle f(x)}$ の最小値を求める最適化問題を考える。 ${\displaystyle x\in S}$ とする。

分枝限定法には2つの手続きが必要である。

分枝

第一は分枝操作である。場合分けにより部分問題に分割する。つまり、与えられた集合 ${\displaystyle S}$ に対して、${\displaystyle S_{1}\cup S_{2}\cup \ldots =S}$ となるような複数の集合 ${\displaystyle S_{1},S_{2},\ldots }$ に分割（分枝）する手続きである。${\displaystyle S_{i}}$ における ${\displaystyle f(x)}$ の最小値を ${\displaystyle v_{i}}$ としたとき、${\displaystyle S}$ における ${\displaystyle f(x)}$ の最小値は ${\displaystyle \min\{v_{1},v_{2},\ldots \}}$ である。この手続きを再帰的に適用することは分枝法 (branching) と呼ばれ、各ノードが ${\displaystyle S}$ の部分集合となるような木（探索木）になる。なお ${\displaystyle S_{i}\cap S_{j}\neq \emptyset }$ でも良い。

限定

第二の手続きは、${\displaystyle S}$ の1つの部分集合 ${\displaystyle S_{i}}$ の ${\displaystyle f(x)}$ の最小値の上限と下限を計算する手続きである。これを限定法 (bounding) と呼ぶ。

分枝限定法の鍵となるのは、あるノード（候補集合） ${\displaystyle A}$ の下限が別のノード ${\displaystyle B}$ の上限より大きければ、A は探索するまでもなく捨ててよいという考え方である。この工程を刈り込み (pruning) と呼び、一般に大域変数 ${\displaystyle m}$ にそれまでに調べた部分の最小の上限値を保持するような実装で実現する。下限が ${\displaystyle m}$ より大きいノードは捨てることができる。

再帰は候補集合 ${\displaystyle S}$ が1つの元になった時点で停止するか、${\displaystyle S}$ の上限が下限と一致した場合に停止する。どちらにしても、停止したときの ${\displaystyle S}$ のどの元も関数を最小値にする。

分枝限定法は、限定法の種類によって分類したり、探索木のノードの生成/検査方法で分類したりする。

分枝限定法の設計戦略は、状態空間木を問題を解くのに使うという点でバックトラッキングとよく似ている。これらの違いは、分枝限定法が木の走査順序を限定していないという点と、分枝限定法が最適化問題でしか使われないという点である。

動的計画法や貪欲法は部分問題の最適性が必要であるが、成立しない部分問題に対して、適切に場合分けして分枝することにより、分枝限定法でうまく行くこともある。

分枝が場合分けをするので並列実装や分散実装に適している。

効率的な分枝

この手法の効率は、ノード分割手続きと上限および下限を推定する手続きに強く依存する。他の全ての条件が同じなら、オーバーラップしない部分集合に分割するのが最もよい。

理想的には、この手続きは探索木の全てのノードが刈りこまれるか解かれたときに停止する。その時点で刈りこまれていない部分は、上限と下限が関数の大域的最小値と等しくなっている。実際には、ある所定の時間が経過すると手続きを停止することが多く、その時点では刈りこまれていない部分の最大下限値と最小上限値が大域的最小値の区間を定義している。これとは別に時間制限ではなく、アルゴリズムを何らかの誤差基準で停止させる方法もある。例えば （最大 - 最小）/（最大 ＋ 最小）がある特定値以下になった時点で停止させる。

この手法の効率は、分枝法と限定法に使われたアルゴリズムの有効性に強く依存する。間違った選択をすると分枝が繰り返され、全く刈り込みが行われず、あまりにも細かく分割されることになる。それは定義域を総当りするのと何ら変わりないことになり、多くの場合現実的でない。あらゆる問題でうまくいく限定法アルゴリズムは存在しないし、今後見つかるとも思えない。従って、分枝法と限定法のアルゴリズムは問題毎に設計する必要がある。

応用

分枝限定法は以下のような問題で使われる。

• ナップサック問題
• 非線型計画問題
• 巡回セールスマン問題 (TSP)
• 二次割り当て問題 (QAP)
• 最大充足可能性問題 (MAX-SAT)
• 最近傍探索 (NNS)

また、各種ヒューリスティクスの基盤でもある。例えば、上限と下限の差がある値以下になったとき分枝を止めたいという場合もある。これは、「実用には十分な」解を求めるのに使われ、必要な計算量を大幅に減らすことができる。特にコスト関数にノイズがある場合や統計的推定に基づくコスト関数にはこのような手法が現実的である。そのようなコスト関数は確率的に誤差を生じる可能性がある。例えば生物学で有機体間の進化的関係を評価する場合、何らかのヒューリスティックを用いないとデータが大きすぎる。

同じ理由で、ゲーム木の探索にも分枝限定法がよく使われ、例えばアルファ・ベータ法は分枝限定法の一種である。

関連項目

• A*
• 設計パラダイムによるアルゴリズムの分類