optimization - 如何优化这个 MiniZinc 应用程序？

Question

我有一个 MiniZinc 应用程序，我想通过找到一些输入数据的低成本排列来最小化某些东西的“成本”。所以我有：

array[1 .. n] of var 1 .. n: Seq;
...
constraint alldifferent( [ Seq[i] | i in 1 .. n ]);

然后我根据 Seq 计算成本。该应用程序开始工作，但运行时间过长，超过了一个非常小的数字。显然求解器尝试了所有 n! 可能性。我如何缩放这个？

Answer 1

如果 alldifferent(Seq) 是唯一的约束，那么求解器将尝试所有排列。

但是，排列中经常存在可能破坏的对称性，例如第一个元素是 1 或第一个元素总是小于第二个元素等。这些对称性通常是非常特定的问题。

如果模型中还有其他约束，那么这些可以帮助减少搜索空间，可能是通过破坏对称性等。

正常情况下 n 有多大？像往常一样，模型的更多细节有助于提供更具体的帮助。此外，尝试不同的求解器和启发式搜索可以加快速度。