分枝価格法

分枝価格法の全容

分枝価格法（ぶんしかかくほう、英: branch and price）は、混合整数計画問題（Mixed Integer Programming）を解決するための有用な組合せ最適化手法です。この手法は、分枝限定法と列生成法を融合したアルゴリズムとして知られており、特に大規模問題に特化しています。

アルゴリズムの概要

分枝価格法の基本的な考え方は、探索木における線形計画緩和問題（LP緩和問題）において、必要に応じて列を逐次追加していくことにあります。この手法は、最初に計算資源を効率的に使用するために、LP緩和問題に対して限られた数の列を使用して開始します。その後、より良い解を得るために、新たな列を再度加えていきます。

興味深い特徴として、大規模な問題においては多くの変数が0になることが挙げられます。これにより、実際には問題を解くために必要な列だけを見つけることが重要になります。

分枝価格法は、通常ダンツィーク・ウルフ分解法によって問題を再定式化し、主問題（Master Problem）を構成することからスタートします。再定式化を行うことで、元の問題の緩和から得られる上下界が向上する可能性があります。しかし、生成される総変数は元の問題の数よりも指数的に多くなるため、部分集合からなる限定主問題（Restricted Master Problem）について考え、それを解くことが求められます。

次のステップでは、限定主問題の解が元の問題の最適性を満たすかどうかを確認するため、価格付け問題（Pricing Problem）と呼ばれる部分問題を解きます。ここでの目的は、基底に追加できる列を見つけ、目的関数を減少させることです。具体的には、負の被約費用を持つ列を探すことが重要です。

価格付け問題は難解な場合もありますが、被約費用が負となる列を見つければ最適性を確認できるため、ヒューリスティック手法や局所探索法を用いることで比較的容易に新たな列を見つけることが可能です。

限定主問題の最適解が主問題の解と一致することを立証するためには、この部分問題を完全に解決する必要があります。負の被約費用を持つ列を発見する度に、それを限定主問題に追加して再びLP緩和問題を解きます。もし基底に追加できる列が存在せず、かつLP緩和問題の解が整数条件を満たしていない場合、分枝操作を実施します。

分枝価格法は、特定の問題に対し効率的な分枝操作と価格付け問題の解決方法を特化させることが求められます。また、分枝価格法では切除平面法を組み込むことも可能であり、これを分枝価格カット法（branch and price and cut）と呼びます。

分枝価格法の応用

分枝価格法は、以下のような様々な問題に適用されています。

• - 配送計画問題: 製品や資源を効率的に配送するための計画を立案します。
• - 一般化割当問題: 複数のリソースを異なるタスクに効率的に割り当てる問題です。
• - グラフ多重彩色問題: ノードに色を割り当て、隣接するノードが同じ色を持たないようにする問題です。この問題の解決を通じて、彩色可能な色の最小数を求めることができます。
• - グラフ多重彩色問題は、ジョブショップ・スケジューリング問題や通信チャネル割当問題など、様々なモデル化に利用されています。

分枝価格法の特性は、その効率性から、多くの実世界の最適化問題において高い効果を発揮しています。

もう一度検索