「分枝価格法」の版間の差分
ナビゲーションに移動
検索に移動
細 ("分枝価格法" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 1行目: | 1行目: | ||
'''【 ぶんしかかくほう (branch-and-price method) 】 | '''【 ぶんしかかくほう (branch-and-price method) 】 | ||
| − | + | 列生成法と[[分枝限定法]]を組み合わせた手法． | |
列生成法で用いるマスター問題は，元の定式化における線形緩和よりも | 列生成法で用いるマスター問題は，元の定式化における線形緩和よりも | ||
（最小化の場合）よい下界値を出す． | （最小化の場合）よい下界値を出す． | ||
| 8行目: | 8行目: | ||
そこで分数変数が得られた場合， | そこで分数変数が得られた場合， | ||
元の定式化でも分数変数が存在する性質を利用している． | 元の定式化でも分数変数が存在する性質を利用している． | ||
| − | + | 1990年代後半から注目を浴び始め，[[一般化割当問題]]， | |
| − | + | 鉄道などの乗務スケジュール問題， | |
| + | 時間枠など制約の付いた車両巡回問題などで成功を収めている． | ||