Skip to content
返回搜索结果

Benders Decomposition

提出者
Jacques F. Benders
年份
1962
类型
algorithm
类别
Optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

Benders Decomposition(由 Jacques F. Benders 于 1962 年提出)是一种强大的算法框架,用于求解大规模混合整数规划 (MIP) 问题。它将问题分解为主问题(控制复杂变量)和子问题(处理剩余变量),并利用从子问题对偶信息生成的割平面来迭代地收紧主问题。

方法背后的直觉

该方法认识到某些变量(称为复杂变量)使得问题难以直接求解,而剩余变量则易于处理。通过固定复杂变量并求解由此产生的剩余变量的子问题,算法获得对偶信息,从而生成割平面。这些割(cuts)加强了主问题,然后主问题会选择更优的复杂变量值。这个迭代过程一直持续到收敛。关键的见解是,分解将一个难题转化为许多更简单的子问题加上一个较小的主问题。

历史学

Benders 于 1962 年引入了他的分解方法,用于划分混合整数规划问题。Geoffrion 于 1972 年推广了该方法以处理非线性问题,创建了现代应用所使用的框架。随着计算能力和求解器的发展,该方法获得了广泛关注。最近的进展包括组合 Benders 割、多割变体以及与现代分支割算法的集成,使其成为高级优化中的基石技术。

何时使用

将 Benders Decomposition 应用于大规模混合整数规划问题,特别是那些具有可分解利用的特殊结构(阶梯形、块角形)的问题。对于直接求解方法在计算上不可行的那些问题,它尤其有效。将其用于设施选址、生产规划和网络设计问题。对于小规模问题或没有特殊结构的问题,直接的 MIP 求解器可能更有效。

局限与注意事项

  • 需要适合分解的问题结构;对于完全通用的问题可能效率不高
  • 割的生成可能产生许多约束,可能减慢主问题的求解速度
  • 收敛可能很慢,需要多次迭代才能达到严格的容差
  • 实现复杂度高于直接求解方法
  • 可能存在割系数的数值稳定性问题

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

优势

  • 有效求解标准方法难以处理的大规模混合整数规划问题
  • 自然地利用具有块角形或阶梯形结构的问题
  • 提供下界和上界,在收敛前即可保证质量
  • 分解允许并行求解独立的子问题
  • 广义 Benders 可处理非线性子问题,拓宽了适用范围

应用

  • 设施选址:确定仓库位置和产品分配以最小化总成本
  • 生产规划:在库存和产能约束下对各设施的生产进行调度
  • 车辆路径规划:在车队构成决策下规划配送路线
  • 网络设计:在电信或交通网络中选择设施、链路和容量
  • 电力系统:在输电约束下进行经济调度和机组承诺决策
  • 供应链优化:协调网络中的采购、生产和分销

使用方式

使用方式

1

设置仅包含复杂变量和占位符约束的主问题。初始化上下界;下界来自主问题,上界来自可行解。

2

将复杂变量固定在其当前值,并求解剩余变量的子问题。如果子问题不可行,则生成可行性割;如果可行,则提取对偶信息并生成最优性割。

3

向主问题添加反映子问题见解的割。重新求解主问题,并重复此过程,直到上下界之间的差距可接受。

常见陷阱

  • 选择不佳的复杂变量,导致子问题难以求解
  • 未能实施稳定技术(信任域、水平集方法)来加速收敛
  • 弱割生成,未能充分加强主问题
  • 忽略预处理和来自可行解的热启动

常见问题

什么是复杂变量,如何识别它们?

复杂变量是指那些固定其值后,剩余问题就容易求解的变量。它们是通过检查问题结构来识别的:出现在耦合独立子问题的约束中的变量,或者在连续问题中出现的离散变量,都是常见的候选。

可行性割和最优性割有什么区别?

当子问题不可行时,会生成可行性割,从而从主问题中消除复杂变量的不可行值。最优性割则整合了可行子问题的对偶信息,以改进主问题的目标估计。

Benders Decomposition 如何保证收敛?

可行性割和最优性割确保了主问题松弛提供了有效的下界。上界来自完整问题的可行解。当界限在容差范围内收敛时,就保证了最优性。对于有界的整数问题,收敛是有限的。

何时 Benders 比直接使用 MIP 求解器求解问题更可取?

当问题规模大、具有可分解利用的特殊结构,或者直接求解器超时时,Benders 更可取。对于小规模问题或缺乏结构的问题,现代 MIP 求解器通常更快、更简单。

相关方法

参考文献

  1. Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

    打开 DOI 文献
    已复制。
  2. Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

    打开 DOI 文献
    已复制。