Eclipse CLP标签：排除排列

Question

我正在解决一个调度问题（这里简要描述：SWI Prolog CLP(FD) scheduling切换到ECLP）。

我能够快速得到一些解决方案，但现在我想要整合一些优化任务。

问题/计划行的一部分看起来像D1,D2,N1,N2,A0,A1,A2,..,A9，这个变量的一些成本是C1,C1,C1,C1,C2,C2,C2,...,C2。因此，从这个角度来看，任何A0..A9任务的排列都有相同的成本。但是，显然，在标记过程中，求解器会回溯所有可能性。

简短说明：我只是在脑海中计算这个，但我认为只有这个描述部分的搜索空间就像大小为15 * 10的域的10个子集的数量！这是一个相当大的空间来回溯。从成本/优化以及约束满足的角度来看，每个排列具有相同的成本/可满足性 - 变量的顺序无关紧要。

我可以以某种方式影响标签/搜索程序，而不必担心某些列表中的变量顺序吗？或者你能提供一些方法来重塑问题，以便能够以这种方式工作吗？

Answer 1

你所谈论的是建模中的对称性问题，并且有一个专门的研究领域。我想说基本上有三种解决方法：

1. 用不同的变量重新建模模型，以便有更少的方法来表示等价的解决方案
2. 添加对称破坏约束以减少解决方案的总数，但保留每个等价类中的至少一个。这通常通过算术或词典排序约束来完成，这有效地定义了解决方案的“规范”表示应该如何。
3. 尝试使用系统提供的动态对称破坏技术，例如ldsb。这些通常采用对称性的描述，并尝试对它做一些事情（但不要指望奇迹）。

在你的情况下，我将从第1点开始：你现在有变量A [I，D] = W意味着“D日的A型插槽I充满工人W”，尽管所有的A插槽都是等效的。

您可以改为使用二进制变量JobA [D，W] = 1“工作人员W在D日执行A类作业”，同时使用约束sum(JobA[D,*])#=10以确保填充了10个插槽。

我能想象的另一个模型是变量Job [D，W] = T“worker W在D日做T型工作”（将你的工作类型T编码为1..3）并使用occurrences/3或gcc/2约束来强制执行各种条件。