分枝価格法

提供: ORWiki
ナビゲーションに移動 検索に移動

【 ぶんしかかくほう (branch-and-price method) 】

列生成法と分枝限定法を組み合わせた手法. 列生成法で用いるマスター問題は,元の定式化における線形緩和よりも (最小化の場合)よい下界値を出す. 一方, マスター問題では,変数が膨大に増加し整数解を得難いが, そこで分数変数が得られた場合, 元の定式化でも分数変数が存在する性質を利用している. 1990年代後半から注目を浴び始め,一般化割当問題, 鉄道などの乗務スケジュール問題, 時間枠など制約の付いた車両巡回問題などで成功を収めている.