在 MiniZinc 中优化多个目标

Question

我是 CP 的新手，但我想解决我在大学遇到的问题。

我有一个 Minizinc 模型，它最大限度地减少了执行某些任务的已使用机器的数量。机器有一些资源，任务有资源需求。除了最小化这个数字，我试图最小化将任务分配给机器的成本（我有一个带有成本的数组）。有没有机会先最小化这个数字，然后在 Minizinc 中优化成本？

例如，我有 3 个任务和 2 台机器。每台机器都有足够的资源来分配 3 个任务，但我想分配成本较低的任务。

对不起我的英语，感谢您的帮助。如果有这样的需要，我会粘贴我的代码。

Answer 1

您所指的技术称为词典优化/目标。这个想法是针对多个目标进行优化，其中目标之间有明确的顺序。例如，在优化时，(A, B, C)我们将优化B和C，服从A。因此，如果我们可以提高 的价值，A那么我们将允许B并C恶化。同样，C也优化受制于B。

这种技术经常使用，但目前（还）在 MiniZinc 中不被原生支持。但是有一些解决方法：

• 如辐射模型所示，我们可以按至少与第二个目标的最大值一样多的值来缩放第一个目标（依此类推）。这将确保第一个目标的任何改进将胜过第二个目标的任何改进/停滞。实例的结果应该是字典序最优的。
• 我们可以将我们的模型分成多个阶段。在每个阶段，我们只关心一个单一的目标值（从最重要到最不重要的工作）。任何后续阶段都会确定早期阶段的目标。最后阶段的解决方案应该为您提供词典最佳解决方案。
• 一些求解器本身支持词典优化。在 MiniZinc 中使用这些词典目标有一些实验支持，如std/experimental.mzn.

请注意，词典编纂技术可能并不总是（明确地）谈论最小化和最大化；但是，您始终可以通过否定预期的目标值来从一种转换为另一种。