本节我们就来讨论在运筹规划如何解决大规模的优化问题。一般会有以下一些方式，我分别进行理解。
- 列生成和分支定价算法
- 拉格朗日松弛算法
- Dantizig-Wolfe分解算法
- Benders分解算法。
列生成和分支定价算法
列生成算法（Column Generation）是一种用于高效求解大规模线性规划（LP）或整数规划（IP）问题的算法，尤其适用于变量数量庞大但大部分变量在最优解中为零的情况。
列生成算法的思想是是通过迭代求解限制型主问题实现全局最优。
求解流程
对偶变量反映了当前解中约束的边际成本。
- 步骤3：求解子问题（定价）
利用对偶变量构建子问题，目标是找到一个或多个能改善主问题目标的新列（即检验数为负的列）。
子问题通常是一个优化问题，例如：最短路径问题（车辆路径规划）。
若子问题目标值（检验数）为负，则将新列加入RMP；否则算法终止（当前解已最优）。
- 步骤4：迭代
重复步骤2-3，直到子问题无法生成改善的列。
完整的求解过程
需求描述：原料长度（L）: 10，长度 3: 需求 4 根，长度 5: 需求 2 根，长度 7: 需求 3 根
步骤 1：初始化主问题（RMP）
- 模式 1: [3, 0, 0]（切 3根长度3，余料1）
- 模式 2: [0, 2, 0]（切 2根长度5，余料0）
- 模式 3: [0, 0, 1]（切 1根长度7，余料3）
$$\begin{gathered}min x_{1} + x_{2} +x_{3} \\
s.t. 3 x_{1}+0x_{2}+0x_{3}>=4 \\
0x_{1}+2x_{2}+0x_{3}>=4 \\
x_{1}+0x_{2}+x_{3}>=4 \\
x_{1} ,x_{2} ,x_{3}>0\end{gathered}$$
步骤 2：第一次迭代
$$\begin{gathered}x_{1}=\frac{4}{3}, x_{2}=1, x_{3}=3 \\
目标值：x_{1} + x_{2} +x_{3}=5.3 \\
对偶变量: 长度3的约束: \pi_{1}=\frac{1}{3}\\
长度5的约束: \pi_{2}=\frac{1}{2}(需求 2 根, x_{2}=1)\\
长度7的约束: \pi_{3}=1 \\\end{gathered}$$
求解子问题（定价问题）,子问题目标: 找到新模式$a=[a_{1}, a_{2}, a_{3},]$ 使得检测数<0.
$$\begin{gathered}检测数=(1-\frac{1}{3} a_{1}+0.5a_{2}+1a_{3}) \\
3a_{1}+5a_{2}+7a_{3}<10\end{gathered}$$
枚举可行模式,[1, 1, 0]（切1根3和1根5，余料2），[0, 0, 1]（已存在，检验数=0），[1, 0, 1]（切1根3和1根7，余料0）
[1, 0, 1]（加入主问题）
步骤 3：第二次迭代
更新主问题
$$\begin{gathered}min x_{1} + x_{2} +x_{3}+x_{4} \\
s.t. 3 x_{1}+0x_{2}+0x_{3}+x_{4}>=4 \\
0x_{1}+2x_{2}+0x_{3}+0x_{4}>=4 \\
x_{1}+0x_{2}+x_{3}+x_{4}>=4 \\
x_{1} ,x_{2} ,x_{3}, x_{4}>0\end{gathered}$$
求解
$x_{1}=1, x_{2}=1,x_{3}=1, x_{4}=1$, 目标值为5， 对偶变量为
$$\begin{gathered}对偶变量: 长度3的约束: \pi_{1}=\frac{1}{3}\\
长度5的约束: \pi_{2}=\frac{1}{2}(需求 2 根, x_{2}=1)\\
长度7的约束: \pi_{3}=\frac{2}{3} \\\end{gathered}$$
求解子问题
模式 7: [0, 2, 0]（切2根5，余料0）
模式 8: [2, 0, 0]（切2根3，余料4
无负检验数模式 → 终止迭代。
步骤 4： 最终解
原料总数: 4 根
切割方案:
模式 1 [3,0,0]: 1 次 → 切出 3根3
模式 2 [0,2,0]: 1 次 → 切出 2根5
模式 3 [0,0,1]: 1 次 → 切出 1根7
模式 6 [1,0,1]: 1 次 → 切出 1根3和1根7
发现1和2是可能方案。
代码
while True:
# 求解当前RMP
cplex.solve()
duals = cplex.getDuals()
# 求解子问题生成新列
new_col, reduced_cost = solve_pricing(duals)
if reduced_cost >= -tol:
break # 最优解找到
else:
cplex.addCols([new_col]) # 添加新列
拉格朗日松弛
拉格朗日松弛是一种用于求解复杂优化问题（尤其是整数规划或混合整数规划）的技术，通过将难处理的约束松弛到目标函数中，转化为更易求解的子问题。其核心思想是：
- 松弛部分约束：将某些复杂约束移入目标函数，通过拉格朗日乘子（对偶变量）惩罚违反约束的情况。
- 分解问题：主问题通过对偶变量调整，子问题因约束减少更易求解。
- 迭代优化：通过次梯度法等更新拉格朗日乘子，逐步逼近原问题的最优解。
适用问题
列生成：动态添加变量（列），适合变量指数级增长的问题（如切割库存）。
拉格朗日松弛：松弛复杂约束，适合约束难以处理的问题（如旅行商问题中的子环消除约束）。
求解过程
资源分配问题， 目标最小化总成本, $\sum c_{j}x_{j}$
约束
- 资源需求约束：$\sum a_{ij}x_{j}>b_{i}$（难处理，选择松弛）。
- $x_{j} \in [0,1]$
拉格朗日松弛
松弛复杂约束：将资源需求约束放入目标函数，引入拉格朗日乘子 $λ_{i}≥0$
$$
L_{λ}=min(\sum_{j} c_{j}x_{j}+\sum_{i}λ_{i}(b_{i}-\sum a_{ij}x_{j}))
$$
分解为子问题：对固定的 λ，子问题变为：
$$
L_{λ}=\sum_{i}λ_{i}b_{i}+min\ \sum_{j}(c_{j}-\sum_{i}λ_{i}a_{ij})x_{j}
$$
子问题可独立求解（如贪心算法）。
更新乘子：用次梯度法调整 λ：
$$
λ_{i}^{k+1}=max(0, λ_{i}^{k}+θ_{k}(b_{i}-\sum_{j} a_{ij}x_{j}^{k}))
$$
其中$θ_{k}$表示步长。
代码展示
import numpy as np
def lagrangian_relaxation():
# 问题数据
c = np.array([3, 5, 2]) # 成本系数
A = np.array([[2, 1, 4], # 资源消耗矩阵
[1, 3, 2]])
b = np.array([5, 4]) # 资源需求
x_bounds = [0, 1] # x_j ∈ {0,1}
# 拉格朗日参数初始化
lambda_ = np.zeros(len(b)) # 初始乘子
max_iter = 100 # 最大迭代次数
best_upper_bound = float('inf')
best_x = None
# 次梯度法迭代
for k in range(max_iter):
# 1. 求解子问题（松弛后的问题）
reduced_cost = c - np.dot(lambda_, A)
x = (reduced_cost < 0).astype(int) # 贪心选择：若减后成本<0则选1
# 2. 计算上界（原问题可行解，若存在）
if np.all(np.dot(A, x) >= b):
current_cost = np.dot(c, x)
if current_cost < best_upper_bound:
best_upper_bound = current_cost
best_x = x.copy()
# 3. 计算下界（拉格朗日松弛值）
L = np.dot(c, x) + np.dot(lambda_, b - np.dot(A, x))
# 4. 更新乘子（次梯度法）
subgradient = b - np.dot(A, x)
step_size = 1.0 / (k + 1) # 动态步长
lambda_ = np.maximum(0, lambda_ + step_size * subgradient)
print(f"Iter {k}: Lower Bound = {L:.2f}, Upper Bound = {best_upper_bound}, x = {x}")
return best_x, best_upper_bound
# 运行示例
solution, cost = lagrangian_relaxation()
print("\nFinal Solution:")
print(f"x = {solution}, Total Cost = {cost}")
总而言之
目前我们介绍了两种办法解决大规模的优化问题，后续还会继续补充另外两种方式。