分枝価格法とは？わかりやすく解説

分枝価格法（ぶんしかかくほう、英: branch and price）とは、（混合）整数計画問題（Mixed integer programming）を解くための組合せ最適化の解法である。分枝価格法は分枝限定法と列生成法を組みわせたアルゴリズムである。

アルゴリズムの説明

分枝価格法は各探索木における線形計画緩和問題（英語版）（LP緩和問題）に対して列を追加し続ける分枝限定法の一種である。アルゴリズムの開始時は計算に必要なメモリ・計算資源を削減するためにLP緩和問題の一部の列のみを使用することから始め、必要に応じて列を緩和問題に再び追加する。分枝価格法で解かれる大規模な問題では列に対応するほとんどの変数が0となることから着想を得ている。これはすなわち大規模な問題ではほとんどの列は問題を解くためには不要な列であり、問題を解くのに必要な列だけを効率よく生成することが重要である。

分枝価格法は一般的にダンツィーク・ウルフ分解法によって問題を再定式化し、主問題（Master Problem）を構成することから始める。再定式化によって元の定式化の緩和を解くより良い上下界を得る可能性を高める。しかし再定式化の総変数は元の問題の総変数と比べておおよそ指数乗個の変数が生成されるため、列の部分集合からなる限定主問題（Restricted Master Problem）を解くことを考える^[2]。続いて限定主問題で得られた解が元の問題での最適性の条件を満たしているかを確認するために、価格付け問題（Pricing Problem）と呼ばれる部分問題を解き、基底に入れることで（最小化問題の場合は）目的関数を減少させる列を探す。具体的に負の被約費用（英語版）を持つ列を見つける必要がある。価格付け問題自体は解くのが難しい場合があるが、被約費用が最も小さい列を必ずしも見つける必要はなく被約費用が負となる列を一つ見つければ最適性を確認することができるため、ヒューリスティック解法や局所探索法によって新たな列を比較的簡単に求めることができる^[3]。なお限定主問題の最適解が主問題の最適解であることを証明するにはこの部分問題を完全に解く必要がある。負の被約費用を持つ列が見つかるたびにその列を限定主問題に追加し、線形計画緩和問題を再び解く。もし基底に追加できる列が存在せず、線形計画緩和問題の解が整数条件を満たさない場合、分枝操作を行う^[1]。

分枝価格法は解く問題に応じて効率的な分枝操作と価格付け問題を解くことを容易にするような定式化を行うなど特化させる必要がある^[4]。

分枝価格法において線形計画緩和問題を解く際に切除平面法を組み込むことも可能である。これは分枝価格カット法（英: branch and price and cut）と呼ばれている^[5]。

分枝価格法の応用

分枝価格法は以下に挙げられる問題とその類似問題に対して応用されている:

配送計画問題^[2]
一般化割当問題（英語版）^[6]
グラフ多重彩色問題^[3]: これはグラフ彩色問題を拡張した問題でグラフの各ノードに対して与えられた数の色を一つ割り当て、隣接するノード間で同じ配色がないような彩色のパターンを求める問題である。この問題を求める目的として与えられた条件下で彩色可能な色の数の最小値を求めることが挙げられる。多重彩色問題はジョブショップ・スケジューリング問題や通信チャネル割当問題などモデル化に応用されている。

脚注

[脚注の使い方]

^ ^a ^b Akella, M.. “Branch and Price: Column Generation for Solving Huge Integer Programs”. 2010年8月21日時点のオリジナルよりアーカイブ。2012年12月19日閲覧。
^ ^a ^b Feillet, Dominique (2010). “A tutorial on column generation and branch-and-price for vehicle routing problems”. 4OR 8 (4): 407–424. doi:10.1007/s10288-010-0130-z.
^ ^a ^b Mehrota, Anuj; M.A. Trick (2007). “A Branch-And-Price Approach for Graph Multi-Coloring”. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series. 37. pp. 15–29. doi:10.1007/978-0-387-48793-9_2. ISBN 978-0-387-48790-8
^ Gamrath, G.. “Generic Branch-Cut-and-Price”. 2022年2月25日閲覧。
^ Desrosiers, J.; M.E. Lubbecke (2010). “Branch-Price-and-Cut Algorithms”. Wiley Encyclopedia of Operations Research and Management Science.
^ Savelsbergh, M. (1997). “A branch-and-price algorithm for the generalized assignment problem”. Operations Research. 831-841 45 (6): 831–841. doi:10.1287/opre.45.6.831.

参考文献

Barnhart, Cynthia; Johnson, Ellis L.; Nemhauser, George L.; Savelsbergh, Martin W. P.; Vance, Pamela H. (1998), “Branch-and-price: column generation for solving huge integer programs”, Operations Research 46 (3): 316–329, doi:10.1287/opre.46.3.316, JSTOR 222825, https://jstor.org/stable/222825

外部リンク

Lecture slides on branch and price
Prototype code for a generic branch and price algorithm
BranchAndCut.org FAQ
SCIP 分枝価格法のフレームワークを持つオープンソースの混合整数計画ソルバー
ABACUS – A Branch-And-CUt System – オープンソースソフトウェア

[lectureSlides-1] Akella, M.. “Branch and Price: Column Generation for Solving Huge Integer Programs”. 2010年8月21日時点のオリジナルよりアーカイブ。2012年12月19日閲覧。

[tutorial-2] Feillet, Dominique (2010). “A tutorial on column generation and branch-and-price for vehicle routing problems”. 4OR 8 (4): 407–424. doi:10.1007/s10288-010-0130-z.

[multicoloring-3] Mehrota, Anuj; M.A. Trick (2007). “A Branch-And-Price Approach for Graph Multi-Coloring”. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series. 37. pp. 15–29. doi:10.1007/978-0-387-48793-9_2. ISBN 978-0-387-48790-8

[4] Gamrath, G.. “Generic Branch-Cut-and-Price”. 2022年2月25日閲覧。

[branchPriceAndCut-5] Desrosiers, J.; M.E. Lubbecke (2010). “Branch-Price-and-Cut Algorithms”. Wiley Encyclopedia of Operations Research and Management Science.

[6] Savelsbergh, M. (1997). “A branch-and-price algorithm for the generalized assignment problem”. Operations Research. 831-841 45 (6): 831–841. doi:10.1287/opre.45.6.831.

[1]

[2]

[3]

[4]

[5]

[6]

分枝価格法とは？わかりやすく解説