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

【だんつぃくうるふぶんかいほう (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}

\] に対する反復法. 制約条件 $\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$個の独立な部分問題を順次解いて, もとの問題の解を求める.