Dantizig-Wolfe分解算法

本章继续介绍大规模优化问题的求解方式。
Dantzig-Wolfe分解（又称列生成法）是一种用于求解大规模线性规划问题（尤其具有块对角结构）的算法，通过将原问题分解为：
主问题（Master Problem）：协调全局资源分配。
子问题（Subproblems）：生成可行的局部解（列），通过定价机制反馈给主问题。
核心思想：利用问题的可分解结构，避免直接处理所有变量，转而动态生成有效列（变量）以逼近最优解。

算法适用场景

约束矩阵呈块对角结构（如资源分配、多商品流问题）。
变量数量庞大，但大多数在最优解中取零值。

经典应用

切割库存问题（Cutting Stock）
车辆路径规划（VRP）
供应链优化

求解方法

原问题

$$min \sum_{k=1}^{K} c_{k}x_{k} \\ s.t. \sum_{k=1}^{K} A_{k}x_{k} >b (耦合约束) \\ x_{k} \in X_{k}$$

分解主问题

利用凸组合表示定理，将 $x_{k}$表示为$X_{k}$的极点点集$\hat{x_{k}^{p}}$的线性组合：

$$x_{k}=\sum_{p \in P_{k}} λ_{k}^{p}\hat{x_{k}^{p}} \\ \sum_{p \in P_{k}} λ_{k}^{p}=1$$

主问题（RMP）：

$$min \sum_{k=1}^{K} \sum_{p \in P_{k}} λ_{k}^{p}(c_{k}\hat{x_{k}^{p}) \\ s.t. \sum_{k=1}^{K} \sum_{p \in P_{k}}}(A_{k}\hat{x_{k}^{p}) λ_{k}^{p} \\ \sum_{p \in P_{k}}} λ_{k}^{p}=1$$

子问题（定价问题）

对每个子问题 k，计算检验数（Reduced Cost）：

$$\hat{c_{k}}=c_{k}-π^{T}A_{k}-μ_{k}$$

π主问题中耦合约束的对偶变量。$μ_{k}$凸性约束的对偶变量。子问题目标：找到极点$\hat{x_{k}^{*}}$ 使得$\hat{c_{k}}\hat{x_{k}^{*}}<0$

$$min(c_{k}-\pi^{T}A_{k})x_{k}$$

迭代优化流程

1. 初始化：构建包含初始可行列的主问题（如人工变量或启发式解）。
2. 求解主问题：得到当前解和对偶变量 (π,μ)
3. 求解子问题：检查是否存在负检验数的列。若存在，将新列加入主问题。否则，当前解为最优。
4. 终止条件：所有子问题的检验数非负。

Benders分解算法

Benders分解是一种用于求解混合整数规划（MIP）或大规模线性规划的算法，通过将问题分解为：
主问题（Master Problem）：处理复杂变量（如整数变量）。
子问题（Subproblem）：固定主问题的变量后，求解剩余线性问题，生成割平面（Benders割）反馈给主问题。
核心思想：利用对偶理论将问题分解为迭代求解的主问题和子问题，通过添加割平面逐步逼近最优解。

算法适用场景

问题特征：

• 变量可划分为“复杂变量”（如整数变量）和“简单变量”（如连续变量）。
• 约束可分离为与复杂变量直接相关的部分和剩余部分。
  使用问题：
  设施选址问题
  供应链网络设计
  多阶段随机规划

求解方法

原问题形式

假设原问题为混合整数规划：

$$min C^{T}x + d^{T}y \\ s.t. Ax+By>b （耦合约束） \\ x \in X \\ y>0$$

分解为子问题和主问题

子问题（固定 x）：给定主问题的解$x^{k}$,求解连续变量y:

$$min d^{T} y \\ s.t. By>b - Ax^{k} \\ y>0$$

若子问题可行，返回最优值$Q(x^{k})$和对偶变量$π^{k}$
若子问题无界，返回极方向$u^{k}$

利用子问题的信息生成Benders割，逐步逼近原问题：

$$min C^{T}x + η \\ s.t. η>(b-Ax)^{T}π^{l} （最优割） \\ 0>(b-Ax)^{T}\mu^{m} \\ x \in X$$

η 是子问题目标值的近似（辅助变量）。

迭代优化流程

• 主问题不含割平面（或添加初始可行割）。
• 设上界UB=+∞ 下界LB=-∞
• 得到当前解$x^{k}$和下界$LB=c^{T}x^{k}+η$
• 固定$x=x^{k}$,求解子问题：
• 若可行：得到$Q(x^{k})$和对偶变量$π^{k}$， 更新上界$UB=min(UB, c^{T}x^{k}+Q(x^{k}))$
• 若无界：得到极方向$\mu^{k}$，添加可行性割到主问题。
• 生成割平面：若子问题可行，添加最优割：$η>(b-Ax)^{T}π^{k}$
• 终止条件：当$UB-LB<\sigma$时停止，否则返回步骤2。

设施选址问题

选择开设工厂(二元决策$x_{i}$),分配运输量（连续变量$y_{ij}$)以满足需求，最小化总成本（固定成本+运输成本）。

$$min \sum_{i} f_{i}x_{i}+\sum_{i,j}c_{ij}y_{ij} \\ s.t. \sum_{i} y_{ij}>d_{j} \\ 0<y_{ij}<M_{x_{i}} \\ x_{i} \in [0,1]$$

Benders分解步骤

• 主问题：决定是否开设工厂$x_{i}$.
• 子问题：固定工厂选址后，求解运输问题$y_{ij}$

迭代过程

1. 主问题初始解：x=[0,1]（假设）。
2. 子问题：检查运输是否可行。
3. 若不可行（如需求未满足），添加可行性割：“至少开设工厂1或2”。
4. 主问题更新：添加割后重新求解，得到新解 x=[1,0]。
5. 重复至收敛。

总而言之

咱们目前就把经常使用的优化方法进行了介绍。