scipy - CPLEX 与使用 SCIP 的 CPLEX 的速度

Question

我是 LP 新手，只PuLP在 Python 中短暂使用过。

1. SCIP 3.2.1 - CPLEX 12.63为什么和之间有速度差异CPLEX 12.6.3？SCIP 不是仍然使用 CPLEX 来求解吗？

2. 为什么有人将 SCIP 与 CPLEX 求解器一起使用，而不是直接使用 CPLEX？

Answer 1

这个区别是什么

该图未显示 LP 基准，而是显示混合整数编程基准。

混合整数规划求解器通常使用基于分支和切割的算法（包括启发式算法和 co.），其中解决了许多松弛（按顺序；将二进制/整数变量视为连续的，从而导致LP 问题）。

然后一个决定是选择如何解决这些宽松的子问题。最简单的决定（还有更多；例如调整Simplex-algorithm的参数；解决非线性圆锥目标问题时变得更加复杂）是选择 LP 求解器。

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

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

为什么将 SCIP 与 CPLEX 一起使用（而不是使用纯 CPLEX 方法）

为什么不那么容易解释。

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

  一些理论的关键词：NP-hardness (of MIP) and the No free lunch theorem

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

• 这两个求解器（MIP 求解器）在参数和可访问性（内部算法组件）方面可能也有很大不同。很明显，您可以以比 CPLEX 更通用的方式调整 SCIP（因为它是开源的）

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