列生成算法 (Dantzig-Wolfe)
- 提出者
- George B. Dantzig and Philip Wolfe
- 年份
- 1960
- 类型
- algorithm
- 类别
- Optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
列生成算法由 George B. Dantzig 和 Philip Wolfe 于 1960 年提出,是一种强大的优化技术,用于解决具有特殊结构的大规模线性规划问题。该方法也称为 Dantzig-Wolfe 分解,它将问题分解为一个主问题(仅限于变量/列的子集)和一个定价子问题(识别新变量),通过引入相关列迭代地改进解决方案。
方法背后的直觉
该方法认识到许多大型优化问题具有特殊结构:变量众多但真正重要的约束很少,或者存在可自然分解的子问题。列生成算法不是解决包含所有可能变量的完整问题,而是仅维护一小部分有前景的列(变量)。定价问题通过使用简化成本和问题结构来解决,识别出可以改进主问题解的新列。通过迭代添加最有前景的列,该算法有效地构建解决方案,避免了同时处理所有列的计算负担。
历史学
Dantzig 和 Wolfe 于 1960 年提出了线性规划的分解原理,奠定了理论基础。Gilmore 和 Gomory (1961) 将其应用于下料问题,展示了其实际效用。该方法在 20 世纪 80 年代至 90 年代在车辆路径和调度问题中获得了突出地位。与分支定界法相结合,创建了分支定价算法,扩展了其在整数规划中的适用性。现代应用包括航空公司乘务调度、船舶路径规划和大规模物流优化。
何时使用
当解决具有特殊结构的大规模线性规划问题时,尤其是在变量数量巨大但一小部分变量主导最优解的情况下,应用列生成算法。它非常适用于下料问题、车辆路径问题、乘务调度和装箱问题。当问题结构允许高效求解定价问题时使用它。对于没有可利用结构或规模适中的问题,标准线性规划求解器更实用。
局限与注意事项
- 要求问题结构能够实现高效的定价子问题求解
- 收敛可能很慢,尤其是在接近最优解时(拖尾效应)
- 定价子问题求解必须可靠且高效,否则会失去效率增益
- 实现复杂性高于标准线性规划方法
- 大对偶值和简化成本可能导致数值稳定性问题
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 解决了因列爆炸而无法通过标准方法解决的大规模问题
- 利用问题结构仅生成相关列
- 在迭代过程中提供解质量的界限
- 天然适用于具有特殊子结构的问题(相同的子问题、对称性)
- 可与分支定界法结合用于整数规划(分支定价)
应用
- 下料问题:在将材料切割成所需尺寸时最小化浪费
- 车辆路径问题:在时间窗和容量限制下优化配送和运输路线
- 乘务调度:将乘务人员分配到航班或班次,以最小化总成本
- 装箱问题:将物品高效地装入容器,以最小化浪费和容器数量
- 排班问题:在考虑可用性和偏好约束的情况下,安排工人轮班
- 航空规划:航班调度、乘务分配和飞机维护协调
使用方式
使用方式
从一个受限主问题开始,该问题仅包含初始可行解所需的列子集。
使用单纯形表求解当前受限主问题的对偶问题。识别简化成本并设置定价子问题,以找到具有负简化成本的变量(用于最小化)。
利用其特殊结构求解定价子问题。如果找到一个具有负简化成本的新列,则将其添加到主问题并重复。如果没有改进的列存在,则当前解为最优解。
常见陷阱
- 选择效率低下的定价子问题算法,抵消了列生成带来的效率增益
- 未能识别适合分解的问题结构,导致性能不佳
- 收敛检测不足或容差过严,浪费迭代次数
- 未实施稳定化技术来解决拖尾效应
常见问题
列生成中的定价问题是什么?它与简化成本有何关系?
定价问题识别具有负简化成本的新变量(列),这些变量可以改进主问题的解。简化成本值来自受限主问题的对偶问题,并指导定价子问题中的搜索。
为什么列生成比解决包含所有列的完整问题更好?
在许多问题中,潜在列的数量是指数级或无限的,使得枚举所有列变得不可能。列生成仅按需生成必要的列,从而大大减少了计算负担。
什么是拖尾效应?如何缓解它?
拖尾效应发生在列生成在接近最优解时进展缓慢,生成许多改进微小的列。稳定化技术(对偶平滑、信任域方法、截止策略)可以减少其影响。
分支定价如何将列生成扩展到整数规划?
分支定价将列生成与分支定界法相结合:在每个节点,列生成求解线性规划松弛问题,当线性规划解为分数时,分支决策进一步限制问题。