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

出典: ORWiki

【だんつぃくうるふぶんかいほう (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 \,個の独立な部分問題を順次解いて, もとの問題の解を求める.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%80%E3%83%B3%E3%83%84%E3%82%A3%E3%82%AF%E3%83%BB%E3%82%A6%E3%83%AB%E3%83%95%E5%88%86%E8%A7%A3%E6%B3%95" より作成