Benders分解.ppt

Benders分解算法 秦术晋 Benders 分解算法 算法介绍 算法描述 一般步骤 混合算法 结合模型的想法 算法介绍 Benders 分解算法是 J.F.Benders 在 1962 年首先提出的，目的是用 于解决混合整数规划问题，即连续变量与整数变量同时出现的极值问 题。但它的实际应用并不限于此，A.M.Geoffrion 建立了广义的 Benders 分解，它可以对具有 Benders 分解基本形式的非线性问题求解，对子问 题的求解方法也不必一定是线性的。Benders 分解算法是一个很常用的 算法，用来计算像最小整数非线性规划问题和随机规划问题之类的难 以计算的难题。 算法介绍 J.F.Benders 设计了一个探索解答具有复杂变量的数学规划问题结 构的一个巧妙途径，所谓的复杂变量是指，当这些变量先固定时，使得 剩下的优化问题（通常为子问题）变得相当容易。在 Benders 考虑的一类 特殊问题中，先把复杂变量的值固定，从而将问题规约为一个一般的线 性规划问题，当然，这个线性规划问题是以复杂变量为参数的。在 Benders 设计的算法里，利用割平面的方式将线性规划问题作为参变量 的函数的极值和使得线性规划问题有可行解的参变量的值的集合很恰 当地表达了出来。过程中，对偶理论用来推导刻画这些表达式的特征的 自然割平面族，而带有参变量的线性规划问题被用来生成割平面。 算法描述 原问题 如何消除x? 约束集 有可行解 等价 线性规划问题有可行解 给定一个 值 对偶 对偶问题的最优目标函数值为0 算法描述 原问题 子问题 原问题的一个Benders子问题 对偶 原问题 等价 原问题的Benders主问题 由当前 求解下面的子问题： 1.无可行解 原问题有无界最优值或无可行解 算法终止 2.有无界的最优值 3.有有限的最优值 一般步骤 得到 一条极线 主问题的松弛问题中加约束： 求新的松弛问题，并得到 和 。令 得到 一个极点 ，令 算法终止 yes no yes 算法终止 no 主松弛问题加约束： 求新问题得 和 令 混合算法 Improving benders decomposition using a genetic algorithm. C.A. Poojari, J.E. Beasley *.European Journal of Operational Research.2009