分枝限定法#
読み: ぶんしげんていほう
英名: Branch and Bound Algorithm
混合整数計画問題において広く使われているアルゴリズム.Lang-Doig らが発見した.
変数の一部を整数に固定した子問題を列挙し,その連続緩和問題を順に解いていくことによって,厳密解を得るアルゴリズム.順に解いていく段階で,最適解の候補となる子問題を絞っていくのが特徴.連続緩和問題を解く際には,単体法がよく使われる.近年は妥当不等式と組み合わせる,ヒューリスティックな解を用いるなどによって高速化が図られている.