Skip to content
返回搜索结果

列生成算法 (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 年代在车辆路径和调度问题中获得了突出地位。与分支定界法相结合,创建了分支定价算法,扩展了其在整数规划中的适用性。现代应用包括航空公司乘务调度、船舶路径规划和大规模物流优化。

何时使用

当解决具有特殊结构的大规模线性规划问题时,尤其是在变量数量巨大但一小部分变量主导最优解的情况下,应用列生成算法。它非常适用于下料问题、车辆路径问题、乘务调度和装箱问题。当问题结构允许高效求解定价问题时使用它。对于没有可利用结构或规模适中的问题,标准线性规划求解器更实用。

局限与注意事项

  • 要求问题结构能够实现高效的定价子问题求解
  • 收敛可能很慢,尤其是在接近最优解时(拖尾效应)
  • 定价子问题求解必须可靠且高效,否则会失去效率增益
  • 实现复杂性高于标准线性规划方法
  • 大对偶值和简化成本可能导致数值稳定性问题

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 解决了因列爆炸而无法通过标准方法解决的大规模问题
  • 利用问题结构仅生成相关列
  • 在迭代过程中提供解质量的界限
  • 天然适用于具有特殊子结构的问题(相同的子问题、对称性)
  • 可与分支定界法结合用于整数规划(分支定价)

应用

  • 下料问题:在将材料切割成所需尺寸时最小化浪费
  • 车辆路径问题:在时间窗和容量限制下优化配送和运输路线
  • 乘务调度:将乘务人员分配到航班或班次,以最小化总成本
  • 装箱问题:将物品高效地装入容器,以最小化浪费和容器数量
  • 排班问题:在考虑可用性和偏好约束的情况下,安排工人轮班
  • 航空规划:航班调度、乘务分配和飞机维护协调

使用方式

使用方式

1

从一个受限主问题开始,该问题仅包含初始可行解所需的列子集。

2

使用单纯形表求解当前受限主问题的对偶问题。识别简化成本并设置定价子问题,以找到具有负简化成本的变量(用于最小化)。

3

利用其特殊结构求解定价子问题。如果找到一个具有负简化成本的新列,则将其添加到主问题并重复。如果没有改进的列存在,则当前解为最优解。

常见陷阱

  • 选择效率低下的定价子问题算法,抵消了列生成带来的效率增益
  • 未能识别适合分解的问题结构,导致性能不佳
  • 收敛检测不足或容差过严,浪费迭代次数
  • 未实施稳定化技术来解决拖尾效应

常见问题

列生成中的定价问题是什么?它与简化成本有何关系?

定价问题识别具有负简化成本的新变量(列),这些变量可以改进主问题的解。简化成本值来自受限主问题的对偶问题,并指导定价子问题中的搜索。

为什么列生成比解决包含所有列的完整问题更好?

在许多问题中,潜在列的数量是指数级或无限的,使得枚举所有列变得不可能。列生成仅按需生成必要的列,从而大大减少了计算负担。

什么是拖尾效应?如何缓解它?

拖尾效应发生在列生成在接近最优解时进展缓慢,生成许多改进微小的列。稳定化技术(对偶平滑、信任域方法、截止策略)可以减少其影响。

分支定价如何将列生成扩展到整数规划?

分支定价将列生成与分支定界法相结合:在每个节点,列生成求解线性规划松弛问题,当线性规划解为分数时,分支决策进一步限制问题。

相关方法

参考文献

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    打开 DOI 文献
    已复制。
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

    打开 DOI 文献
    已复制。