列生成算法

1. 基本概念
   列生成是一种用于求解大规模线性规划问题的高效算法，尤其适用于变量数量极大（甚至指数级）但大部分变量在最优解中取值为零的情况。其核心思想是仅维护一个变量子集（称为限制主问题），通过求解子问题动态添加可能改善目标函数的变量，避免枚举所有变量。

2. 适用场景与动机
   典型应用包括切割库存问题、航班调度等。例如，在切割库存问题中，可能的切割方案数量随材料尺寸增长呈指数级增加，但列生成只需在每一步考虑当前最有价值的方案，大幅降低计算量。

3. 算法流程

   • 步骤1：初始化一个包含部分变量的限制主问题（RMP），保证其可行。
   • 步骤2：求解RMP，得到对偶变量值（如影子价格）。
   • 步骤3：求解子问题（定价问题），寻找一个未被加入RMP的变量，其检验数（约化成本）为负（对最小化问题），即满足：

\[ c_j - \mathbf{\pi}^T \mathbf{A}_j < 0 \]

其中 \(c_j\) 是变量系数，\(\mathbf{\pi}\) 是对偶变量，\(\mathbf{A}_j\) 是约束系数列。

• 步骤4：若找到此类变量，将其加入RMP并返回步骤2；否则当前解即为原问题最优解。

4. 关键点与收敛性

   • 子问题的目标通常是最小化约化成本，其本质是寻找可能进基的变量。
   • 收敛性依赖于对偶理论：当无负约化成本的变量时，满足互补松弛条件，达到最优。
   • 常与分支定界法结合（分支定价）求解整数规划。

5. 实例说明
   以切割库存问题为例：

   • RMP：选择有限切割方案满足订单需求。
   • 子问题：生成一个新方案，使每单位材料的“收益”（由对偶变量加权需求）最大。
   • 若子问题目标值大于材料成本，则新方案可加入RMP。