使用SCIP实现CPLEX与CPLEX的速度

Question

我对LP很陌生，在Python中只短暂地使用过PuLP。

1. 为什么SCIP 3.2.1 - CPLEX 12.63和CPLEX 12.6.3之间存在速度差异？SCIP是否仍然使用CPLEX来解决问题？
2. 为什么有人会在CPLEX解决器中使用SCIP，而不是直接使用CPLEX？

​

​

Answer 1

这有什么区别？

此图不是LP基准测试，而是混合整数编程基准。

混合整数规划求解器通常使用branch-and-cut-based算法(包括启发式和协同)，其中大量求解松弛(按顺序；将二进制/整数变量视为连续的，从而产生LP问题)。

其中一个决定就是选择如何解决这些轻松的子问题。最简单的决策(还有更多的，例如，调整Simplex-algorithm's参数；在解决具有非线性锥目标的问题时会变得更加复杂)是选择LP-求解器。

SoPlex是由SCIP团队实现的LP解决方案.意思：

• SCIP - SoPlex将使用SCIP的算法对MIP (处理分支，切割生成和合作)用SoPlex求解内部LP-子问题
• SCIP将使用SCIP的MIP算法，使用CPLEX作为内部LP子问题的求解器。

为什么在CPLEX中使用SCIP (而不是使用纯CPLEX方法)

为什么不那么容易解释。

• 要记住，所有的MIP求解器都是基于启发式的，并且在某些问题上SCIP将比CPLEX更快(尽管选择了底层的LP-解决器)。 某些理论关键词：NP-硬度 (of MIP)和无自由午餐定理

- Faster could mean: faster due to the MIP-based strategies, not the speed of the underlying LP-solver so that you may even gain an overall speedup using CPLEX on the subproblems!

​

• 这两个求解器(MIP-求解器)在参数和可访问性(内部算法组件)方面可能也有很大的不同。很明显，您可以以比CPLEX更通用的方式优化SCIP (因为它是开源的)。
• 正如mattmilten在注释中提到的那样: SCIP和CPLEX在问题类的支持方面也不同，这些问题类是可以解决的。这方面的一个例子可能是某些特殊非线性约束 (导致MINLP)的可能性。对于这类问题使用SCIP，仍然可以在内部使用CPLEX‘LP-解决器(与上面相同的参数)。