Dantzig–Wolfe 分解#
読み: だんつぃぐうぉるふぶんかい
英名: Dantzig–Wolfe Decomposition
線形計画問題において,実行可能領域の端点,端線の情報を用いて得られる等価な別の定式化.例えば次の線形計画問題
(13)#\[\begin{split}\begin{array}{ll}
\min & c^\top x \\
\text{s.t.} & Ax \le b
\end{array}\end{split}\]
において,実行可能領域 \(Ax \le b\) の端点が \(v_i, \ i \in I\),端線が \(d_j, \ j \in J\) であるとする.このとき,実行可能領域 \(Ax \le b\) は
(14)#\[\left\{ \sum_{i \in I}{\lambda_i v_i} + \sum_{j \in J}{\mu_j d_j} \ \mid \ \sum_{i \in I}{\lambda_i} = 1, \ \lambda_i \ge 0, \ \mu_j \ge 0 \right\}\]
と表現できる.これを用いると,元の線形計画問題は次のように定式化できる.
(15)#\[\begin{split}\begin{array}{ll}
\min & c^\top \left( \sum_{i \in I}{\lambda_i v_i} + \sum_{j \in J}{\mu_j d_j} \right) \\
\text{s.t.} & \sum_{i \in I}{\lambda_i} = 1, \ \lambda_i \ge 0, \ \mu_j \ge 0
\end{array}\end{split}\]
関連