本节我们就来讨论在运筹规划如何解决大规模的优化问题。一般会有以下一些方式，我分别进行理解。

• 列生成和分值定价算法
• 拉格朗日松弛算法
• Dantizig-Wolfe分解算法
• Benders分解算法。

列生成和分值定价算法

列生成算法（Column Generation）是一种用于高效求解大规模线性规划（LP）或整数规划（IP）问题的算法，尤其适用于变量数量庞大但大部分变量在最优解中为零的情况。
列生成算法的思想是是通过迭代求解限制型主问题实现全局最优。

求解流程

• 步骤1：初始化构建一个初始的限制主问题（RMP），仅包含少量可行列（如人工变量或启发式生成的列）。
  例如，在切割库存问题中，初始列可能是简单的切割模式。

• 步骤2：求解限制主问题
  使用线性规划求解器（如CPLEX、Gurobi）求解当前RMP，得到对偶变量值（影子价格）。

对偶变量反映了当前解中约束的边际成本。

• 步骤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）

$$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$$

步骤 2：第一次迭代

$$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 \\$$

求解子问题（定价问题）,子问题目标: 找到新模式$a=[a_{1}, a_{2}, a_{3},]$ 使得检测数<0.

$$检测数=(1-\frac{1}{3} a_{1}+0.5a_{2}+1a_{3}) \\ 3a_{1}+5a_{2}+7a_{3}<10$$

枚举可行模式,[1, 1, 0]（切1根3和1根5，余料2），[0, 0, 1]（已存在，检验数=0），[1, 0, 1]（切1根3和1根7，余料0）
[1, 0, 1]（加入主问题）

步骤 3：第二次迭代

更新主问题

$$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$$

求解
$x_{1}=1, x_{2}=1,x_{3}=1, x_{4}=1$, 目标值为5， 对偶变量为

$$对偶变量: 长度3的约束: \pi_{1}=\frac{1}{3}\\ 长度5的约束: \pi_{2}=\frac{1}{2}(需求 2 根, x_{2}=1)\\ 长度7的约束: \pi_{3}=\frac{2}{3} \\$$

求解子问题
模式 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])  # 添加新列

拉格朗日松弛

拉格朗日松弛是一种用于求解复杂优化问题（尤其是整数规划或混合整数规划）的技术，通过将难处理的约束松弛到目标函数中，转化为更易求解的子问题。其核心思想是：

1. 松弛部分约束：将某些复杂约束移入目标函数，通过拉格朗日乘子（对偶变量）惩罚违反约束的情况。
2. 分解问题：主问题通过对偶变量调整，子问题因约束减少更易求解。
3. 迭代优化：通过次梯度法等更新拉格朗日乘子，逐步逼近原问题的最优解。

适用问题

列生成：动态添加变量（列），适合变量指数级增长的问题（如切割库存）。
拉格朗日松弛：松弛复杂约束，适合约束难以处理的问题（如旅行商问题中的子环消除约束）。

求解过程

资源分配问题， 目标最小化总成本, $\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}")

总而言之

目前我们介绍了两种办法解决大规模的优化问题，后续还会继续补充另外两种方式。