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

Question

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

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

Answer 1

虽然有一种方法可以设置我们搜索变量的预选顺序(input_order 变量选择试探法)，但目前没有值选择试探法可以对搜索变量的顺序执行相同的操作值被尝试。

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

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

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

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