播种 CP-SAT 求解器

Question

在谷歌 OR-tools 库中，“原始”CP-Solver（此处讨论： https: //developers.google.com/optimization/cp/original_cp_solver）可以使用重新播种.ReSeed()。然而，较新的版本，CP-SAT 不能。

我的假设是 CP-SAT 将详尽地尝试您问题中的每个选项，从可行的选项中选取最大值或最小值（取决于您的优化目标）。因为它会尝试所有这些，所以不需要做种，因此该选项对您不可用。

这种理解正确吗？如果是的话，为什么原始求解器有种子？.ReSeed()如果我的说法不正确，那么新 CpSolver 中缺少 是否是一个疏忽？

Answer 1

不，你的推理不太正确。

是的，CP-SAT 求解器将尝试每个选项，并在有限时间内找到解决方案或证明不可行（在某些温和条件下：除了提到最简单的限制 -> 内存之外，我不会尝试详细说明；不太简单：随机重启进程）。求解器的这种性质通常被称为完整且（健全）（后者指的是当可行时永远不会出现像不可行这样的错误分类输出）。但原始的 CP-Solver 也是完整且健全的。

播种永远不应该用作调整参数（并且用例非常有限）。种子被用作PRNG -init（解算器中存在随机性，但它是确定性的），并且在比赛中使用这一事实可能是有意义的（以渲染运气或无用的调整）。

正如@Stradivari 的评论中提到的， protobuf 定义中有一个种子。如果您愿意，这些也可以设置。

它可能看起来像这样：

from ortools.sat.python import cp_model

solver = cp_model.CpSolver()
solver.parameters.random_seed = 10

这显示了 python 接口，但 protobuf 文件是针对所有受支持的语言进行编译的，因此这些 setter 应该在所有 API 中可用（恕我直言）。

如果我没记错的话，手动设置的参数将在求解开始时显示给您（或者有某种方法可以获取此信息以进行一些额外的检查）。