optimization - 如何将启发式算法融入 MiniZinc 中？

Question

假设我有一个订单批处理问题(在仓库环境中)，我想借助启发式方法来解决。特别是，我想为具有多个交叉 channel 的仓库实现一些著名的启发式算法，例如 S 形和最大间隙启发式算法。

如何在 MiniZinc 中实现它们？可以这样做吗？

我查了它的文档，但只能找到 MiniSearch，这是一种在 MiniZinc 模型中指定元搜索的语言。 (http://www.minizinc.org/minisearch/documentation.html)

对此的一些见解将受到深深的赞赏。

Answer 1

您的问题的答案在很大程度上取决于您的启发式的性质。从 MiniZinc 方面，我将确定三种启发式方法:

1. 求解启发式算法:求解模型实例的启发式算法，但可能无法给出最佳解决方案。
2. 搜索启发式:启发式算法提供(良好)指示下一步最好搜索的内容。
3. 部分启发式:可以求解部分模型实例，但无法求解完整模型实例的启发式。

没有直接的 MiniZinc 方法来处理启发式方法，您可能需要一些创造力来以可用的方式实现您的启发式方法。以下是一些可能的解决方案:

如果您正在处理启发式求解，您可能不需要做任何工作；它已经给你一个解决方案。但是，如果您想验证解决方案或确保最佳解决方案，那么您可以考虑使用该解决方案运行模型或使用该解决方案作为热启动(分别)。 (如果它足够广泛，您甚至可以将启发式实现为 FlatZinc 求解器，但要考虑时间投入与可用性。)

在其他两种情况下，众所周知的解决方案是预先计算启发式并将其包含在模型数据中。在搜索启发式的情况下，可以计算搜索变量的顺序。然后，您可以在 input_order 搜索启发式中使用此顺序。对于部分启发式，可以预先计算部分模型并将其直接包含在模型中。这对于问题来说往往过于受限。相反，如果您可以计算多个部分解决方案，则可以将它们作为表约束包含在内。

只有当启发式算法不依赖于搜索中变量的域时，以前的解决方案才有可能。当他们这样做时，我们通常谈论“元搜索”。这就是像 MiniSearch 这样的实现的出现。在 MiniSearch 中，您可以例如反射(reflect)最后一个解决方案或最后一个分配，并根据这些值建立新的搜索行为。这使得这些更加动态的启发式方法得以实现。

即使 MiniSearch 通常也不会在每个节点上运行。因此，在某些情况下，您可能无法直接在 MiniZinc 中使用启发式方法。在这种情况下，一个选项是将启发式添加到 FlatZinc 求解器，然后使用指定的注释调用它。