Dantizig-Wolfe分解算法
本章继续介绍大规模优化问题的求解方式。
Dantzig-Wolfe分解（又称列生成法）是一种用于求解大规模线性规划问题（尤其具有块对角结构）的算法，通过将原问题分解为：
主问题（Master Problem）：协调全局资源分配。
子问题（Subproblems）：生成可行的局部解（列），通过定价机制反馈给主问题。
核心思想：利用问题的可分解结构，避免直接处理所有变量，转而动态生成有效列（变量）以逼近最优解。
算法适用场景
约束矩阵呈块对角结构（如资源分配、多商品流问题）。
变量数量庞大，但大多数在最优解中取零值。
经典应用
切割库存问题（Cutting Stock）
车辆路径规划（VRP）
供应链优化
求解方法
原问题
$$\begin{gathered}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}\end{gathered}$$
分解主问题
利用凸组合表示定理，将 $x_{k}$表示为$X_{k}$的极点点集$\hat{x_{k}^{p}}$的线性组合：
$$\begin{gathered}x_{k}=\sum_{p \in P_{k}} λ_{k}^{p}\hat{x_{k}^{p}} \\
\sum_{p \in P_{k}} λ_{k}^{p}=1\end{gathered}$$
主问题（RMP）：
$$\begin{gathered}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\end{gathered}$$
子问题（定价问题）
对每个子问题 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}
$$
迭代优化流程
- 初始化：构建包含初始可行列的主问题（如人工变量或启发式解）。
- 求解主问题：得到当前解和对偶变量 (π,μ)
- 求解子问题：检查是否存在负检验数的列。若存在，将新列加入主问题。否则，当前解为最优。
- 终止条件：所有子问题的检验数非负。
Benders分解算法
Benders分解是一种用于求解混合整数规划（MIP）或大规模线性规划的算法，通过将问题分解为：
主问题（Master Problem）：处理复杂变量（如整数变量）。
子问题（Subproblem）：固定主问题的变量后，求解剩余线性问题，生成割平面（Benders割）反馈给主问题。
核心思想：利用对偶理论将问题分解为迭代求解的主问题和子问题，通过添加割平面逐步逼近最优解。
算法适用场景
问题特征：
- 变量可划分为“复杂变量”（如整数变量）和“简单变量”（如连续变量）。
- 约束可分离为与复杂变量直接相关的部分和剩余部分。
使用问题：
设施选址问题
供应链网络设计
多阶段随机规划
求解方法
原问题形式
假设原问题为混合整数规划：
$$\begin{gathered}min C^{T}x + d^{T}y \\
s.t. Ax+By>b （耦合约束） \\
x \in X \\
y>0\end{gathered}$$
分解为子问题和主问题
子问题（固定 x）：给定主问题的解$x^{k}$,求解连续变量y:
$$\begin{gathered}min d^{T} y \\
s.t. By>b - Ax^{k} \\
y>0\end{gathered}$$
若子问题可行，返回最优值$Q(x^{k})$和对偶变量$π^{k}$
若子问题无界，返回极方向$u^{k}$
利用子问题的信息生成Benders割，逐步逼近原问题：
$$\begin{gathered}min C^{T}x + η \\
s.t. η>(b-Ax)^{T}π^{l} （最优割） \\
0>(b-Ax)^{T}\mu^{m} \\
x \in X\end{gathered}$$
η 是子问题目标值的近似（辅助变量）。
迭代优化流程
- 主问题不含割平面（或添加初始可行割）。
- 设上界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}$)以满足需求，最小化总成本（固定成本+运输成本）。
$$\begin{gathered}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]\end{gathered}$$
Benders分解步骤
- 主问题：决定是否开设工厂$x_{i}$.
- 子问题：固定工厂选址后，求解运输问题$y_{ij}$
迭代过程
1. 主问题初始解：x=[0,1]（假设）。
2. 子问题：检查运输是否可行。
3. 若不可行（如需求未满足），添加可行性割：“至少开设工厂1或2”。
4. 主问题更新：添加割后重新求解，得到新解 x=[1,0]。
5. 重复至收敛。
总而言之
咱们目前就把经常使用的优化方法进行了介绍。