分枝限定法

分枝限定法#

  • 読み: ぶんしげんていほう

  • 英名: Branch and Bound Algorithm

混合整数計画問題において広く使われているアルゴリズム.Lang-Doig らが発見した.

変数の一部を整数に固定した子問題を列挙し,その連続緩和問題を順に解いていくことによって,厳密解を得るアルゴリズム.順に解いていく段階で,最適解の候補となる子問題を絞っていくのが特徴.連続緩和問題を解く際には,単体法がよく使われる.近年は妥当不等式と組み合わせる,ヒューリスティックな解を用いるなどによって高速化が図られている.