引言

D-W分解是单纯性法创始人Dantizg和凸优化理论创始人Wolfe在上世纪60年代提出的一种针对具有块状对角结构的大规模线性规划模型（P）的分解算法。这个方法的基本思想就是用Minkowski定理将（P）中简单约束集分解为该简单约束集极点的凸组合和极射线的非负组合，将模型做等价转换，从维度庞大的原始变量空间转换到维度低的多的凸组合空间。更重要的是，使用D-W对（P）进行分解后的模型（MP）又恰好能够使用列生成算法进行求解，且由于模型具有独特的块状对角结构，使得我们可以同时产生多个（这个个数就是简单约束对应矩阵块的个数）定价子问题并行计算，又进一步加速了列生成算法求解（MP）的进程。

关于一些缩写的说明

  1. P：Primal Problem，在本文指的就是还没有用D-W分解处理的那个原始的模型。
  2. MP：Master Problem，在本文指的是用D-W分解对P进行处理后得到的那个模型。
  3. RMP：Restricted Master Problem，这是列生成算法中的概念，指的就是只考虑MP中部分列时的模型。
  4. SP：Subproblem，这时列生成算法中的概念，指的是用来获取MP中列的定价子问题。

理论

Minkowski定理

Definition 1. 如果集合中某个点不能由该集合中任意两点的凸组合所表示，那么就说这个点是这个集合的一个极点。
Definition 2. 假设是以集合中某一点为起点的向量，如果对于任意正实数都始终使得始终没有射出这个集合，那么这个就是集合在那一点的一个方向。
Definition 3. 如果是集合中某一点的方向，并且始终不能被其它方向的非负组合表示，那么这样一个方向就是这集合的一个极方向。
Theorem 1. 任意多面体都可以分解为极点的凸组合加上极方向的非负组合。

Minkowski定理的直观解释

以上图为例，极方向的非负组合张成的区域就像一个探照灯，假设我们手拿着探照灯，那么极点的凸组合就控制着手的位置，当我们将手从极点移动到极点，探照灯就把这个非闭的多面体中所有的点都照射到了。对于封闭的多面体（不存在极方向），则只需要使用极点就能将其分解。

D-W分解算法

适合用D-W分解处理的模型的特征

DW分解能处理的问题一定是对变量进行分组，然后对约束系数矩阵做对应分块处理之后出现块状对角结构的线性规划模型。约束系数矩阵中那些独立矩阵块对应的约束一般称为简单约束，而非独立块们所对应的约束则一般称为coupling constraint（复杂的耦合约束）。记为第组变量构成的一个变向量，为第组变量对应耦合约束部分的系数矩阵 ，为第组变量对应简单约束部分的系数矩阵，为第组变量的价值系数构成的行向量，为资源限量构成的列向量。

D-W分解的步骤

设表示的是第组变量对应简单约束集中的极点，是对应简单约束集中极点的个数，是第组简单约束集中第个极点的凸组合系数。

利用Minkowski定理分解简单约束集

对于第组变量对应的简单约束集，

根据Minkowski定理可将其分解为，

将分解结果代回原模型(P)

对结果稍加整理和变形，得到（MP）,

使用列生成算法求解D-W分解得到的(MP)

记，表示目前已知第组变量对应简单约束集中的极点的索引的集合，得到（RMP），

注意到，（MP）模型中变量对应的列是一个维的向量，这个向量的第1维是，第维的分量是1，其它维的分量都是0。而又是已知的，所以我们其实只需要确定就可以确定对应的列。而是第组变量对应简单约束的极点，所以需要满足，定价子问题（SP）的目标给（RMP）提供能使其目标值更优的列，所以定价子问题的目标函数就是去最小化检验数（因为RMP是最小化问题）。又由于（RMP）独特的块状对角结构，我们可以同时得到个（独立矩阵块的个数）定价子问题，其中第个定价子问题的形式如下，，记为第组变量对应第个凸组合系数的检验数，为复杂耦合约束对应的对偶变量构成的向量，是第个独立块对应简单约束的对偶变量（标量）。

实战

续上，