1

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

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

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

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

我可以以某种方式影响标签/搜索过程，以免打扰某些列表中的变量顺序吗？或者你能提供一些方法来改造问题以便能够以这种方式工作吗？

4

1 回答 1

2

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

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

在您的情况下，我将从第 1 点开始：您当前有变量A[I,D]=W表示“D 日类型 A 的插槽 I 被工人 W 填充”，尽管您的所有 A 插槽都是等效的。

您可以改为使用二进制变量JobA[D,W]=1 “worker W 在第 D 天完成类型 A 的工作”，以及sum(JobA[D,*])#=10确保您有 10 个插槽已填满的约束。

我可以想象的另一个模型是有变量Job[D,W]=T "worker W does work of type T on day D"（将您的工作类型 T 编码为 1..3）并使用occurrences/3或gcc/2约束执行您的各种条件。

于 2019-04-26T14:24:49.197 回答