python - 播种 CP-SAT 求解器

Question

在 google 的 OR-tools 库中，可以使用.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 文件是为所有受支持的语言编译的，因此这些设置器应该在所有 API 中都可用（恕我直言）。

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