分枝価格法

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

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