DW分解（Dantzig-Wolfe decomposition）和benders分解
#! https://zhuanlan.zhihu.com/p/598626208 # DW分解（Dantzig-Wolfe decomposition）和benders分解
DW分解（Dantzig-Wolfe decomposition）
对于标准形式的线性规划，也就是
\[ \min c^T x \\ {s.t.}\left \{ \begin{array}{l} Ax = b\\ x\ge 0 \end{array} \right. \]
如果矩阵\(A\)存在一些特点，是有助于我们解决问题的。特别的，如果矩阵形如
也就是存在大量“整块儿”的零矩阵。在这种情况下问题可以写为
\[ \min c_1^T x_1 + c_2^T x_2 \\ {s.t.}\left \{ \begin{array}{l} D_1x_1 + D_2x_2 = b_0\\ F_1x_1 = b_1\\ F_2x_2 = b_2\\ x_1,x_2\ge 0 \end{array} \right. \]
其中\(b_0 \in R^{m_0}\)，\(b_1 \in R^{m_1}\)，\(b_2\in R^{m_2}\)。如果\(m_1,m_2 \gg m_0\)，也就是零矩阵的区域非常大，我们可以使用DW分解来高效的求解。它的本质是利用多面体表示定理（Minkowski Resolution Theorem），把\(x_1\)和\(x_2\)分别进行表示，这样可以转化掉\(F_1x_1=b_1\)和\(F_2x_2=b_2\)这两个约束。但是会引入非常多新的变量。具体的
对于多面体（此处其实是超平面）
\[ \Omega_i = \{x|F_ix = b_i\} \]
我们可以利用Minkowski Resolution Theorem，也就是多面体表示定理，把\(x_1,x_2\)利用多面体的极点和极线表示出来
\[ x_i = \sum_{p^j \in P_{i}} \lambda_i^jp^j + \sum_{r^k\in R_i} \theta_i^kr^k,\quad \sum_{p^j \in P_{i}} \lambda_i^j = 1 \]
其中\(P_i\)是多面体\(\Omega_i\)的极点集，\(R_i\)是多面体\(\Omega_i\)的极线集。基于此，就能写出分解后问题
\[ \min c_1^T(\sum_{p^j \in P_{1}} \lambda_1^jp^j + \sum_{r^k\in R_1} \theta_1^kr^k) + c_2^T (\sum_{p^j \in P_{2}} \lambda_2^jp^j + \sum_{r^k\in R_2} \theta_2^kr^k) \\ {s.t.}\left \{ \begin{array}{l} D_1(\sum_{p^j \in P_{1}} \lambda_1^jp^j + \sum_{r^k\in R_1} \theta_1^kr^k) + D_2(\sum_{p^j \in P_{2}} \lambda_2^jp^j + \sum_{r^k\in R_2} \theta_2^kr^k) = b_0\\ \sum_{p^j \in P_{i}} \lambda_i^j = 1, \ i=1,2\\ \lambda_i^j,\theta_i^k\ge 0 \end{array} \right. \]
注意到这个问题变的只有\(m_0+2\)个等式约束。当然相应的，变量多了很多。我们知道对于这种问题，使用列生成算法是一个很好的方案。
当然，这种方式是可以推广的。首先，它不仅可以处理这种把矩阵分解成两块的情况，更多块也是可以的，也就是把原问题分解成
\[ \min \sum_i c_i^T x_i \\ {s.t.}\left \{ \begin{array}{l} \sum_i D_ix_i = b_0\\ F_ix_i = b_i\\ x_i\ge 0 \end{array} \right. \]
另一方面，它不止能处理等式情况，实际上只要相应集合是可以写成多面体的形式，就可以使用此方法。
benders分解
DW分解是利用列生成的方式对问题进行分解，对偶的，benders分解利用行生成的方式解决问题。实际上，benders分解和DW分解某种程度上也存在一种对偶性。
考虑问题P
\[ \min f(x,y) \\ {s.t.}\left \{ \begin{array}{l} G(x,y) \ge 0 \\ x\in X,y\in Y (X\subseteq R^{n_1},Y\subseteq R^{n_2}) \end{array} \right. \]
其中，x为普通变量，y为特殊变量，一般为比x更复杂的变量。比如常见的x为普通变量，y为整数变量。
当y被暂时的固定下来时，问题P就可以被分解为独立的子问题，这些问题可以被并行求解。并且由于这些子问题只包含普通变量，它们是好求解的；甚至可以被reduce到已有的问题（背包问题、最短路问题、普通线性规划）。这两此决策往往是上下层的关系。
基于这个思想，我们可以把问题重写为 \[ \min_y\ [\min_x f(x,y)\ s.t. G(x,y) \ge 0 , x\in X]\\ s.t.\ y\in Y\cap V \] 或者说，更清晰的 \[ \min_y\ v(y)\\ s.t.\ y\in Y\cap V \]
其中\(v(y)=\min_x f(x,y)\ s.t. G(x,y) \ge 0 , x\in X\)，\(Y = \{y:G(x,y)\ge 0\ for \ some \ x \in X \}\)
在传统的Benders分解中，要求\(v(y)\)是一个线性规划问题。
如果我们假设子问题\(v(y)\)是一个线性规划问题，也就是 \[ v(y) = \min_{x\in X} f(x,y) = \min_{x\in X} c^T x + \psi(y)\\ s.t. \ G(x,y) = Ax + g(y) + b \ge 0,x\ge 0 \]
写出它的对偶问题 \[ v(y) = \max_{u\ge0} \psi(y) - u^T g(y) - u^T b\\ s.t. \ c^T - u^T A \ge 0,u\ge 0 \]
注意一些对偶问题的性质：对偶问题的任意目标值是原问题任意目标值的下界（这也是要取对偶问题的关键之一）；对偶问题无界->原问题无解。
考虑对偶问题的极值点集\(\Omega_p\)和极值束集\(\Omega_r\) 对于极值点集，我们有 \[ v(y) \ge \psi(y) - u^T (g(y)+b),\forall u \in \Omega_p \] 对于极值束集，当\(u\in \Omega_r\)，对偶问题无界，原问题无解。 到此为止，主问题\(\min_{y\in Y} v(y)\)就可以写成关于y的带大量约束的问题，其中约束包括种 \[ v(y) \ge \psi(y) - u^T (g(y)+b) , \forall u\in \Omega_p \quad 最优性约束\\ - u^T (g(y)+b) \le 0, \forall u \in \Omega_r \quad 可行性约束 \]
现在我们把原问题转化成了一个含有大量约束的问题，不过问题中不再含有x了。一个非常有用的洞见是绝大多数约束都是不起作用的，只需要找到起作用的约束即可因此我们考虑把这些约束全部松弛掉，然后慢慢加入约束来得到可行解。我们称这个松弛问题为RMP。
求解RMP，得到\(\bar{y}\)和\(v(\bar{y})\)，如果子问题有界，且目标函数值小于等于\(v(\bar{y})\)，这就得到了最优解。若目标函数值大于\(v(\bar{y})\)，则添加最优性约束。若子问题无界，则添加可行性约束。
考虑子问题不是线性规划的形式，我们也可以借用Benders分解的思想。比如使用logit cut来割平面，或使用梯度（次梯度）来近似等。