分枝価格法

提供: ORWiki
2007年9月19日 (水) 22:54時点におけるSaru (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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