我可以指定变量尝试可能值的顺序吗？

Question

我正在 Minizinc 上对巨大的数据集执行聚类，但我的计算时间很长，我正在尝试减少它。为此，我想指定为变量尝试可能值的顺序。

例如，一个变量v作为一个域1..5，但我知道4比3更有可能，3比2更有可能，等等。在这种情况下，有没有办法让我说我想先尝试 4，然后是 3，然后是 2，等等？

Answer 1

尽管有一种方法可以设置搜索变量的预选顺序（input_order变量选择启发式），但目前还没有值选择启发式可以对尝试值的顺序执行相同的操作。

然而，MiniZinc 中还有许多其他值选择启发式：https://www.minizinc.org/doc-2.5.5/en/lib-stdlib.html#value-choice-annotations。如果您正在寻找一种可移植的值选择启发式方法，那么您可能会找到一种近似于您正在寻找的问题的分布的方法。

附带说明一下，最好考虑什么在 CP 求解器中实际上表现最好。虽然选择最有可能的候选者可以带来好的结果，但有时最好的搜索策略实际上是快速失败。如果您知道至少某些变量必须采用不太可能的值，并且证明失败比找到解决方案更容易，那么通常最好先尝试会导致失败的选择。这些失败将迅速进一步推进搜索，在哪里找出一个好的猜测不是解决方案可能需要大量搜索。最后，最好的办法是尝试多种搜索启发式方法。什么最有效可能常常让您感到惊讶。

其他一些需要考虑的事情：

• 如果您不需要便携式解决方案，那么您可以查看哪些值选择启发法可用于各个求解器。某些解算器会在包含文件中添加解算器特定选项以及解算器名称（例如chuffed.mzn和gecode.mzn）。其中包括一些搜索启发式方法。
• 您可以尝试使用“学习求解器”。Chuffed 和 OR-Tools 等 LCG 求解器将从搜索过程中先前的失败中生成新的约束（布尔子句）。这种机制可以显着减少搜索空间并模拟更智能的搜索启发式。
• 如果您可以想象一种启发式方法可以为您的问题提供部分或初步解决方案，您可以尝试 MiniZinc 的热启动功能（https://www.minizinc.org/doc-2.5.5/en/mzn_search.html#warm-starts） 。并非所有求解器都支持这一点。