CPLEX 求解器具有非常高的鲁棒性和可靠性，能够解决高达数百万个变量和约束的求解问题， 是解决大型困难模型的首选， 甚至在某些大型问题上是唯一的可行选择。

算法特点

CPLEX 具有许多复杂的功能，可以极大地提高求解性能，其中包括：复杂的问题预处理、高效的重新启动、敏感性分析、不可行性查找器等。

线性规划

CPLEX 拥有一系列解决 LP 问题的方法，通常，对于大多数问题来说，最佳方法是 CPLEX 的对偶单纯形算法。 某些类型的问题可能会受益于 CPLEX 的原始单纯形算法。 CPLEX 还包含内点法，其 Barrier 算法提供了解决线性问题的单纯形法的替代方法，它基于原始对偶预测校正器方法。 当用于解决大型问题或问题可能存在数值不稳定问题时，通常会考虑使用障碍算法。 还有一种高效的网络单纯形方法可以有效地求解网络模型。

二次规划

CPLEX 可以求解具有二次目标函数和线性约束的模型。 如果目标函数是半正定的，则可以使用任何 LP 方法。 要通过 CPLEX 求解 MPL 中的 QP，必须在 MPL 中将“ModelType”设置为 Quadratic。

混合整数规划

CPLEX 混合整数优化器提供了解决混合整数变量（一般或二进制）问题的功能。 它采用最先进的算法和技术。 CPLEX 主要使用分支剪切算法，该算法本质上解决了一系列松弛的 LP 子问题。 在这些子问题上可以采用添加切割和复杂的分支策略，以尝试更有效地找到最佳解决方案。 CPLEX 还具有启发式方法，可以帮助找到初始的良好解决方案，它还包括复杂的混合整数预处理系统。 人们甚至可以快速有效地解决大型且困难的整数问题。

性能调优

  • LP线性规划

CPLEX 经过调整，可以使用默认选项解决绝大多数 LP 问题。 有时可能需要更改选项设置，这通常是性能不佳或数值不稳定问题的结果。 总的来说，对偶单纯形法最适合大多数线性规划问题，在某些情况下，原始单纯形法可能效果最好。 障碍法通常应用于非常大的稀疏模型或遇到数值困难的模型。 筛选算法是一种简单的列生成形式，非常适合变量数量大大超过约束数量的模型。 LP 上的不良性能是使用简并结果，这可以通过检查迭代日志来识别，具有长迭代序列，其中目标值保持不变。 扰动可以帮助提高退化问题的性能。 对于屏障方法来说，简并性不是问题，因此高度简并的问题应该使用屏障算法来解决LP。

  • MIP混合整数规划

MIP 问题可能非常难以解决，尽管没有关于增强 MIP 性能的固定规则，但某些事情可能有利于提高某些模型的性能，而对其他问题可能会造成阻碍。 以下是尝试解决 MIP 难题时应考虑的一些注意事项：

  • Priority orders: 为应该尽早决定的整数变量分配更高的优先级，这些变量往往代表战略性或激活流程的决策。 MPL中定义的变量的顺序表示MIP的优先级，定义越早优先级越高。

  • Cutoffs: 设置截止值可以大大加快过程，截止值（等于或差于真实最优值的已知值）可以从针对同一问题或先前未完成的 MIP 模型运行的一些启发式算法获得。 使用“MipUpperCutoff”为最小化问题设置上截止值，并为最大化问题设置“MipLowerCutoff”值。

  • Probing: 这着眼于修复二进制变量的逻辑含义，这发生在预求解之后但分支定界之前。 CPLEX 具有 3 个探测级别，这里存在一个权衡因素，即虽然更密集的探测可以获得良好的结果，但也可能需要一些时间才能完成探测。 对于大型困难问题，我们建议使用级别 3 或 2，因为探测的时间开销更有可能通过分支定界的长时间运行时间得到回报。

  • Variable Selection: 选择要分支的变量可以带来相当大的好处。 在困难的模型中，“强分支”或“伪降低成本”可能会有所帮助。 这两种方法（特别是强分支）都投入了大量精力来分析潜在分支，以期大幅减少将要探索的节点数量。

  • Cuts: 增加削减是最近 MIP 性能大幅提高的主要原因之一。 剪切可以显着增加最佳边界并删除树中其他次优的分支。 添加的切割越多，固有矩阵就变得越大，这会增加节点处的处理时间。 然而，通常在困难的模型上，积极的削减策略是最好的练习模式。

 

有关 CPLEX 的更多信息，请访问IBM网页 IBM CPLEX Optimizer.