列生成

1. 为什么要用列生成算法

1.1 适用问题

列生成（Column Generation）是一种用于求解大规模整数/组合优化问题的有效算法。它特别适用于具有以下特征的问题：

• 变量数量极其庞大：问题的决策变量数量随问题规模指数增长，无法显式枚举所有变量
• 约束数量相对较少：相比变量数量，约束条件的数量较小
• 隐式变量结构：许多变量在最优解中值为零，只有少数变量会真正被使用

典型应用场景包括：

问题类型	说明
下料问题（Cutting Stock Problem）	原材料切割方案数量庞大，无法枚举所有可能的切割模式
车辆路径问题（VRP）	可能的路径组合爆炸性增长
机组排班问题	可能的航班组合/工作人员排班方案数量巨大
多维背包问题	物品组合方式过多
集合覆盖/划分问题	子集数量随元素数量指数增长

1.2 核心思想

列生成的核心思想是延迟列生成（Delayed Column Generation）：

不一次性考虑所有可能的决策变量（列），而是从少量变量开始，按需动态生成可能改善目标函数的变量（列），直到无法找到更优的列为止。

这种思想将原问题分解为两个相互交互的子问题：

• 主问题（Master Problem）：在已有列的集合上求解线性规划，得到当前最优解和对偶变量
• 子问题/定价问题（Pricing Problem）：根据主问题的对偶信息，寻找检验数为负的新列（如果存在）

---

2. 求解下料问题的列生成模型

2.1 下料问题的一般描述

给定长度为 的 个棒材，以及 种长度的棒材需求：

• 第 种需求的长度为
• 第 种需求的需求量为

目标：如何切割，使得使用的棒材原料最少？

2.2 直接建模（整数规划形式）

引入决策变量：

• ：第 个棒材是否被使用
• 且为整数：从棒材 上切割获得第 种需求尺寸材料的数量

模型：

其中：

• (1) 最小化使用的棒材数量
• (2) 每种需求必须被满足
• (3) 棒材 的切割长度之和不超过原棒材长度

2.3 列生成建模

上述直接模型中，切割方案（即变量组合）数量巨大。通过列生成，将其转化为主问题和子问题两个阶段：

• 第1阶段（子问题）：决策要使用哪些切割方案（产生哪些列）
• 第2阶段（主问题）：决策按每种切割方案去切割的棒材数量

2.3.1 主问题（Master Problem）

决策变量：

• ：使用切割方案 的棒材数量

参数：

• 且为整数：在切割方案 中第 种尺寸的棒材数量（由子问题获得）

模型：

2.3.2 子问题/定价问题（Pricing Problem）

定价子问题的任务是选出检验数为负的切割方案。

参数：

• ：主问题(5)中第 个约束(6)的对偶变量（第 种需求的数量约束的对偶变量），在定价子问题中为已知参数
• 且为整数：表示在当前切割方案中第 种尺寸的棒材的数量

模型：

注意：子问题的目标函数值 即为检验数。当该值 时，表示找到了可以改善主问题的列。

2.4 列生成算法流程

┌─────────────────┐
│  子问题/定价问题  │
│  (生成新列)      │
└────────┬────────┘
         │
    新列 (检验数<0)
         │
         ▼
┌─────────────────┐
│     主问题      │
│ (求解LP,获得对偶) │
└────────┬────────┘
         │
    对偶变量 π_i
         │
         ▼

算法步骤：

1. 初始化主问题：添加一些初始可行的列（可用启发式算法生成，或简单添加观察到的可行列）

2. 迭代求解：

   • 求解主问题（线性规划松弛），获得当前最优解和对偶变量
   • 将对偶变量传递给子问题
   • 求解子问题：寻找检验数为负的新列
   • 若找到检验数 的列：将其加入主问题，继续迭代
   • 若不存在检验数 的列：算法终止，主问题已最优

3. 整数化处理（如果需要整数解）：

   • 使用分支定界（Branch-and-Price）或直接对最终主问题取整

---

3. 列生成最优性的几个问题

3.1 误差来源：松弛与遗漏求解策略

为了提升效率，列生成算法在处理整数主问题时，通常会采用"先松弛后求整"的策略：

1. 松弛阶段：先将整数约束松弛，将主问题变为线性规划（LP）求解，获取对偶变量传递给子问题生成新列
2. 循环迭代：不断生成检验数为负的新列，直到无法改善为止
3. 求整阶段：对最终生成的限制性主问题（RMP, Restricted Master Problem）重新施加整数约束进行求解

非最优的原因：

使用线性规划的检验数来近似评估整数规划的改进空间会带来误差。这种"先松弛后求整"的操作，很可能会导致原整数规划最优解对应的基变量（列）没有被完全加入到 RMP 的可行列集合 中。因此，仅从这些"比较好"的列中求出的整数解，不一定是全局最优解。

关键理解

列生成算法在 LP 阶段找到的列，只是对 LP 最优解"有用"的列。但对于最终的整数规划最优解，可能还需要其他列才能构成完整的基。

3.2 RMP 达到最优的条件判断

最优情况

当列生成结束时，如果最终 RMP 的线性松弛问题的最优解恰好是纯整数解（所有变量取整数值），那么此时 RMP 的解就是原问题的全局最优解。即当前的凸包 已经包含了最优解。

非最优情况

如果线性松弛最优解是小数，且全局上下界存在差距，说明：

• 遗漏了构成整数最优解所需的关键基变量
• 当前的 RMP 无法等价代表原问题
• 需要采用 Branch-and-Price（分支定价） 算法继续搜索

注意

情况	判定条件	结论
达到最优	RMP 的 LP 松弛解为纯整数	当前解为全局最优
未达最优	RMP 的 LP 松弛解含小数	需进一步分支或补充列

延伸阅读

当列生成的 RMP 线性松弛解含有小数时，需要采用分支定价（Branch-and-Price）算法来寻找整数最优解。详见 分支定价算法。

---

备忘

（在此补充 Dantzig–Wolfe 分解、收敛与实现要点。）