分枝限定法#

読み: ぶんしげんていほう
英名: Branch and Bound Algorithm

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

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