optimization - 如何在 MiniZinc 中加入启发式算法？

Question

假设我有一个订单批处理问题（在仓库环境中），我想借助启发式方法来解决。特别是，我想为具有多个交叉通道的仓库实施一些众所周知的启发式方法，例如 S 形和最大间隙启发式方法。

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

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

对此的一些见解将不胜感激。

标签： optimizationheuristicsminizinc

Answer 1

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

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

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

如果您正在处理启发式求解，您可能不需要做任何工作；它已经为您提供了解决方案。但是，如果您想验证解决方案或确保获得最佳解决方案，则可以考虑使用解决方案运行模型或将解决方案用作热启动（分别）。（如果它足够广泛，您甚至可以将启发式算法实现为 FlatZinc 求解器，但请考虑时间投资与可用性。）

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

只有当启发式算法不依赖于搜索中的变量域时，上述解决方案才有可能。当他们这样做时，我们通常会谈论“元搜索”。这是 MiniSearch 之类的实现。例如，在 MiniSearch 中，您可以反映上一个解决方案或上一个分配，并根据这些值建立新的搜索行为。这允许实现这些更动态的启发式方法。

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