Branch and Bound(分枝限定法)法
分枝限定法とは、組合せ計画問題で厳密解を求めるための手法の1つです。組合せ計画問題とは、ある関数を最大化するパラメータの組の様に、パラメータの有限個の組み合わせの中から目的を満たす組を求める問題です。分枝限定法は、条件分岐を駆使して問題を部分問題にどんどん分割してきます。これを分枝操作といいます。ある部分問題において、これ以上解を探索する必要がないと判断した(部分問題を解いた)場合、部分問題の分割を止めます。これを限定操作といいます。これにより、分枝限定法は探索時間の削減を図ります。部分問題の解は暫定解と呼ばれ、各部分問題を解いた時点での最良の解と言えます。探索する必要がないと判断する条件は下記の通りです。
- 既に最適解が得られた
- 現在の暫定解よりも良い解が得られる可能性がなくなった
- 許容解が存在しないことがわかった(つまり実行不可能)= その条件分岐が不適当だということがわかった
なお部分問題を解く際、分枝限定法は問題の制約条件を緩和することで、問題を解きやすくします。緩和後の問題は緩和問題と呼ばれます。緩和問題は元の問題の条件を緩和しただけなので、緩和問題の解元々の問題の解となります。そのため緩和問題の解を求めた後に修正することで、最終的に元の問題の解を得られることができます(できることが多いそうです)。緩和の例は下記の図に記載の様に、不連続な値域→連続的な値域に変えるのが一般的なようです。
分枝限定法のフローは、下図のチャートの通りです。
なお分枝限定法を実装する場合、下記を検討する必要があります。
- 探索
- どのような順番で部分問題を選ぶか → 一般的なのは最良優先探索(最も良い許容解が得られそうな部分問題を優先)、深さ優先探索(部分問題の深さがより大きい問題を優先)
- 限定操作
- 実行不可能性の判定方法
- 緩和問題の解き方
- 分枝操作
- 問題の分解方法
今回は概念の話に終始しましたが、具体例が必要という場合は[3]を見ると良い気がします。
# 参考文献
[1]http://www.ie.u-ryukyu.ac.jp/~e085739/_downloads/H22.Math.Prog.No.7.pdf
[2]http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp11/mp11-06.pdf
[3]http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout05.pdf