ダンツィク・ウルフ分解法

【だんつぃくうるふぶんかいほう (Dantzig-Wolfe decomposition method)】

行列 $A_{j}\,$, $B_{j}\,$, ベクトル $a\,$, $b_{j}\,$, $c_{j}\,$ により定義されるブロック型の線形計画問題

${\begin{array}{lll}{\mbox{min.}}&\displaystyle {\sum _{j=1}^{n}c_{j}^{\top }x_{j}}&\\{\mbox{s.t.}}&\displaystyle {\sum _{j=1}^{n}A_{j}x_{j}=a,}&\\&\displaystyle {B_{j}x_{j}=b_{j},}&j=1,\ldots ,n,\\&\displaystyle {x_{j}\geq 0,}&j=1,\ldots ,n\end{array}}\,$

に対する反復法. 制約条件 $\textstyle \sum _{j=1}^{n}A_{j}x_{j}=a\,$ の単体乗数ベクトル $\pi \,$ に対して,

${\mbox{min.}}\ \ (A_{j}^{\top }\pi +c_{j})^{\top }x_{j}\quad {\mbox{s.t.}}\ \ B_{j}x_{j}=b_{j},x_{j}\geq 0\,$

という $n\,$個の独立な部分問題を順次解いて, もとの問題の解を求める.