Dantzig-Wolfe 分解

Dantzig-Wolfe 分解（Dantzig-Wolfe Decomposition）是一种将大规模线性规划问题分解为若干小规模子问题求解的方法，特别适用于约束矩阵具有块角结构（Block Angular Structure）的问题。

适用于什么问题

当 线性规划 的约束矩阵呈 块角 / 耦合-独立 结构：少量「中心」或 耦合行 把多块决策向量连在一起，而各块内部约束彼此分离时，用 DW 把各可行域用极点（及必要时极射线）的凸组合表示，可在 主问题 里只显式保留耦合行与凸组合权重，子问题只在各块上求解小规模 LP。典型：多工厂 / 多部门资源统筹（全局产能或物料平衡耦合一组本地生产可行域）、多商品流 / 多周期 在局部守恒与全局耦合并存的紧凑 LP、以及作为 列生成 的理论核心出现在 分支定价 等整数扩展里。

主要局限：经典叙述针对 LP；混合整数情形通常改为 分支定价 或与其它整数框架结合。若矩阵并无明显块角或耦合行占比极高，分解收益有限。若各子可行域极点数爆炸，列生成仍可能很重。

---

1. 块角模型

1.1 问题形式

考虑下面的线性规划问题：

其中，约束矩阵 具有如下块角结构：

1.2 结构说明

块角矩阵由以下部分组成：

块	说明	对应约束
	第一行块（中心约束/耦合约束）	连接所有决策变量的全局约束
	对角块（独立约束）	各子系统独立的局部约束
	决策变量分块	对应各子系统的变量
	右端项分块	对应各约束的右端项

对应约束：

核心思想

Dantzig-Wolfe 分解算法的思想就是将上述模型进行分解，而不是考虑所有约束一起求解。将问题分解为主问题和若干子问题进行求解：

• 主问题：考虑中心的约束条件
• 子问题：进行分开求解，每个子问题只处理自己的独立约束

这样只有一系列更小规模的问题需要求解。

---

2. Minkowski 表示定理

2.1 多面体的表示

考虑子问题线性规划问题的可行域：

2.2 有界情况

如果 是有界的，那么可以将任意点 表示成 的极点 的线性凸组合形式：

其中：

• ： 的第 个极点（顶点）
• ：对应极点的凸组合系数

2.3 无界情况

如果可行域 不是有界的，则需要引入极射线：

其中：

• ： 的第 条极射线
• ：极射线的非负系数

2.4 统一形式

上述表述可以写作如下统一的形式（Minkowski 表示定理）：

其中：

约束 即上文提到的凸约束。

关键理解

通过上述形式可以把原问题关于变量 的形式转换为关于变量 的形式。实际上，随着变量 的数量增多，此模型逐渐变得不能直接求解，这正是列生成算法的用武之地。

---

3. 分解后的主问题

3.1 变量替换

利用 Minkowski 表示，将原变量 用新的变量 表示：

其中 是 的所有极点的索引集合。

3.2 限制主问题（RMP）

将上述表示代入原问题，得到限制主问题（Restricted Master Problem, RMP）：

其中：

• ：当前已知的极点子集（通常 很小）
• ：极点 对应的目标函数值（作为成本系数）
• ：极点 对应的耦合约束系数

3.3 主问题的特点

特点	说明
变量数	理论上等于所有极点的总数（非常庞大）
约束数	中心约束数 + 凸约束数 （相对较少）
求解方式	列生成算法：从少量列开始，按需生成新列

---

4. 子问题（定价问题）

4.1 子问题的作用

子问题的任务是寻找具有负检验数的极点，即寻找可以改善主问题目标函数的列。

4.2 子问题形式

对于每个子系统 ，定义子问题：

或等价地：

其中：

• ：主问题中心约束的对偶变量（ 维向量）
• ：主问题第 个凸约束（）的对偶变量（标量）
• ：简化成本（reduced cost）

4.3 检验数计算

对于极点 ，其检验数为：

列生成的终止条件：所有子问题的最优值 ，即不存在检验数为负的极点。

---

5. 算法流程

5.1 准备阶段：模型重构

首先，你需要把原问题（Original Problem）改造成 主问题（Master Problem）。

• 输入：原问题的约束拆分为"公共约束 "和"局部约束 "。
• 变换：将变量 用局部约束集合的极点 的凸组合表示：，其中 。
• 目标：把这个表示式代入原目标函数和公共约束，得到只含有权重 的模型。

5.2 第一阶段：寻找初始可行基（两阶段法）

算法不能凭空开始，你需要至少一个极点来启动。

• 引入人工变量：如你之前看到的，在 RMP 的公共约束中加入人工变量 ，目标函数设为 。
• 迭代循环：按照列生成的逻辑（见下文第二阶段）不断加入新列。
• 结束标志：如果人工变量的最小值达到了 0，说明你找到了一个（或一组）能够满足所有约束的初始极点。这时候，删掉人工变量，正式进入第二阶段。

5.3 第二阶段：核心迭代循环（列生成）

这是 DW 算法最精彩的部分，它是一个在 受限主问题 (RMP) 和 子问题 (Pricing Subproblem) 之间跳华尔兹的过程：

第一步：求解当前 RMP

解当前的 RMP 模型，获得两个关键的对偶值（Dual Values）：

• ：对应公共约束（Linking Constraints）的对偶价格。
• ：对应凸组合约束（）的对偶值。

第二步：求解子问题（Pricing）

利用拿到的 ，构造子问题的目标函数：

在局部约束 内求解这个子问题。这个过程是在寻找：有没有哪一个极点 ，能够让主问题的目标函数进一步下降？

第三步：判断与入基

• 如果子问题的最优值 （以最小化为例）：
  • 说明找到了一个"好方案"！
  • 将这个极点 转化成 RMP 的一列新数据（即一个新的变量 ），返回第一步。
• 如果子问题的最优值 ：
  • 说明在当前的资源价格 下，已经没有任何新方案能让成本更低了。
  • 算法收敛，达到全局最优。

5.4 结果还原：回到物理变量

当你拿到了最优的 后，最后一步是把这些权重重新加权到对应的极点上，还原回原问题的变量：

这就是你最初想要的 的具体数值。

---

6. 与列生成的关系

6.1 等价性

Dantzig-Wolfe 分解本质上就是列生成算法的一种特殊应用：

Dantzig-Wolfe 分解	列生成算法
分解后得到的主问题	限制性主问题（RMP）
子问题寻找极点	定价问题寻找负检验数列
极点的凸组合	列的线性组合
子问题的可行域	列的生成空间

6.2 优势

• 降维：将大规模问题分解为若干小规模子问题
• 并行：各子问题可以独立求解，易于并行化
• 结构利用：充分利用问题的块角结构

---

备忘

（在此补充 Dantzig-Wolfe 分解的收敛性分析、整数规划扩展、实际应用案例等内容。）