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 可处理非线性子问题,拓宽了适用范围
应用
- 设施选址:确定仓库位置和产品分配以最小化总成本
- 生产规划:在库存和产能约束下对各设施的生产进行调度
- 车辆路径规划:在车队构成决策下规划配送路线
- 网络设计:在电信或交通网络中选择设施、链路和容量
- 电力系统:在输电约束下进行经济调度和机组承诺决策
- 供应链优化:协调网络中的采购、生产和分销
使用方式
使用方式
设置仅包含复杂变量和占位符约束的主问题。初始化上下界;下界来自主问题,上界来自可行解。
将复杂变量固定在其当前值,并求解剩余变量的子问题。如果子问题不可行,则生成可行性割;如果可行,则提取对偶信息并生成最优性割。
向主问题添加反映子问题见解的割。重新求解主问题,并重复此过程,直到上下界之间的差距可接受。
常见陷阱
- 选择不佳的复杂变量,导致子问题难以求解
- 未能实施稳定技术(信任域、水平集方法)来加速收敛
- 弱割生成,未能充分加强主问题
- 忽略预处理和来自可行解的热启动
常见问题
什么是复杂变量,如何识别它们?
复杂变量是指那些固定其值后,剩余问题就容易求解的变量。它们是通过检查问题结构来识别的:出现在耦合独立子问题的约束中的变量,或者在连续问题中出现的离散变量,都是常见的候选。
可行性割和最优性割有什么区别?
当子问题不可行时,会生成可行性割,从而从主问题中消除复杂变量的不可行值。最优性割则整合了可行子问题的对偶信息,以改进主问题的目标估计。
Benders Decomposition 如何保证收敛?
可行性割和最优性割确保了主问题松弛提供了有效的下界。上界来自完整问题的可行解。当界限在容差范围内收敛时,就保证了最优性。对于有界的整数问题,收敛是有限的。
何时 Benders 比直接使用 MIP 求解器求解问题更可取?
当问题规模大、具有可分解利用的特殊结构,或者直接求解器超时时,Benders 更可取。对于小规模问题或缺乏结构的问题,现代 MIP 求解器通常更快、更简单。