CPLEX速度与使用SCIP的CPLEX速度

Question

我对LP很新，并且只是简单地使用过Python中的PuLP。

1. 为什么SCIP 3.2.1 - CPLEX 12.63和CPLEX 12.6.3之间存在速度差异？难道SCIP仍然使用CPLEX来求解吗？

2. 为什么有人会使用带有CPLEX求解器的SCIP，而不是直接使用CPLEX？

- Nyxynyx

---

一些备注：cbc（最好的开源MIP求解器之一）通常将是pulp的默认求解器。至少在Windows发行版中是如此。 - sascha

Answer 1

这个区别是什么

这个图表不展示LP基准，而是混合整数规划基准。

混合整数规划求解器通常使用基于分支定界的算法（包括启发式和其他内容），其中大量的松弛问题被解决（依次处理二进制/整数变量作为连续变量的情况，导致一个LP问题）。

然后，您需要选择如何解决这些松弛子问题。最简单的决策（还有许多其他决策；例如调整Simplex算法的参数；当解决具有非线性锥形目标的问题时会变得更加复杂）是选择LP求解器。

SoPlex是SCIP团队的LP求解器实现。意味着：

• SCIP-SoPlex将使用SCIP的MIP算法（处理分支、割生成等），并使用SoPlex作为内部LP子问题的求解器
• SCIP-CPLEX将使用SCIP的MIP算法，并使用CPLEX作为内部LP子问题的求解器

为什么要使用带有CPLEX的SCIP（而不是纯CPLEX方法）

为什么不是那么容易解释。

• 请记住，所有MIP求解器都是基于启发式的，在某些问题上，SCIP将比CPLEX更快（尽管选择的底层LP求解器不同）。

  一些理论的关键词：MIP的NP难度和“No free lunch theorem”。

  • 更快可能意味着：由于MIP策略更快，而不是底层LP求解器的速度，因此使用CPLEX在子问题中可能会获得整体加速！

这两种求解器（MIP求解器）在参数和算法内部组件的可访问性方面可能也有很大的不同。显然，您可以通过更一般的方式对SCIP进行调整，而CPLEX就不行（因为它是闭源的）。

正如mattmilten在评论中提到的那样：SCIP和CPLEX在支持可解问题类方面也有所不同。其中一个例子可能是某些特殊非线性约束的可能性（导致MINLP）。对于这些类型的问题，使用SCIP仍然可以在内部使用CPLEX的LP求解器（与上述相同的论点）。

- sascha

---

值得注意的是，SCIP可以解决各种问题类别——比CPLEX更多——有时在解决非凸MINLP时仍然使用CPLEX作为LP求解器可能会更有优势。 - mattmilten

@mattmilten 我刚刚添加了一条备注，即有时基于MIP的算法更快，并且通过使用CPLEX的LP求解器来解决子问题可以获得额外的加速。我同意你所说的一切。 - sascha