《ERP高级计划》书的解读―APS算法分析之三分枝界定法（B&B）（二）（蔡颖）

切位（Cutting-Planes） 

切位方法是由B&B开始但是被松散问题的约束定义的可行区域限制朝向一方案移动。

增加约束的建立如

－不可行方案是切断

－最后非整数方案是切断

纯切位算法的趋势是慢慢达到一个方案 

分枝和切（Branch and Cut）

结合 B&B 算法和切位方法：在每一步处理时有点象B&B,但是在每一个树的节点上，而不是在单一变量的分枝上，其算法加上切到问题，其问题是LP可行区域的切断部分。此可行区域是没有切断任何有效整数方案 

B&B 比较 B&C:

－B&C 需要更多的数学内容，因为切断的建立是非常困难的

APS主要采取的是 B&C，ILOG 支持 B&C，自动检查模型是否允许某些标准的切断。

MILP 和LP比较的不利处 ：计算时间， 内存消耗 。所以可以采用启发和分解技术的使用

计算运行时间和内存消耗依赖于问题的复杂性。

复杂性分类：

－P: 算法属于多项式时间复杂类P，如果运行时间可以被一多项式函数界定输入长度。线性时间复杂的算法是快的，因为它们的运行时间刚好是时间的倍数对于读入的数据。 如果它们需要处理大量问题，用二次方程的算法或甚之用立方时间也许会引起运行时间问题

－NP, NP-难题: 另外重要时间复杂类是NP (多项式的非-确定). 大部分的优化问题以 NP-出名. NP问题可以在 用指数时间来解决。然而，只能没有证实的相信，它们在多项式时间里不能解决和难以处理。  

－NP-问题式: 销售员旅行问题, 排程问题, 整数线性优化,.....

－多项式时间问题是: 物流问题(象配置问题，运输问题), 线性优化.....

－全局优化: 由单一和分枝& 切断方法来找到; 还可以用约束传播(CP), 基因算法(GA), 和 Tabu 搜寻 (TS)法找到。

(待续)

本文由作者向AMT提供
蔡颖 专栏