|
切位（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提供 |