python - 播种 CP-SAT 求解器

Question

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

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

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

Answer 1

不，你的推理不太正确。

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

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

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

它可能看起来像这样:

from ortools.sat.python import cp_model

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

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

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