Eclipse CLP标记:排除排列 [英] Eclipse CLP labeling: exclude permutations

问题描述

我正在解决调度问题(在此处简要描述: SWI Prolog CLP(FD)调度切换为ECLP).

I am solving a scheduling problem (briefly described here: SWI Prolog CLP(FD) scheduling switched to ECLP).

我能够快速获得一些解决方案，但是现在我想加入一些优化任务.

I am able to get some solution quickly, but now I want to incorporate some optimization task.

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

A part of the problem/schedule row looks like D1,D2,N1,N2,A0,A1,A2,..,A9 where some cost for this variables is C1,C1,C1,C1,C2,C2,C2,...,C2. So from this point of view any permutation of assignments to A0..A9 has the same cost. But, obviously, during the labeling process the solver backtracks through all the possibilities.

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

Short note: I am calculating this only in my head, but I think the search space only for this described part is like number of subsets of size 10 from domain of size 15 * 10!. This is quite some amount of space to backtrack through. And from the point of view of cost/optimization as well as the constraint satisfaction, each permutation has the same cost/satisfiability - the order of variables does not matter.

我可以以某种方式影响标签/搜索过程，以免打扰某些列表中的变量顺序吗?还是可以提供一些方法来重塑问题，使其能够以这种方式工作?

Can I somehow affect the labeling/search procedure to do not bother with order of variables within some list? Or can you provide some way how to remodel the problem to be able to work this way?

推荐答案

您正在谈论的是建模中的对称性问题，并且有一个专门研究整个问题的领域.我要说的基本上是三种解决方法:

What you are talking about is the issue of symmetry in modelling, and there is a whole research area dedicated to it. I would say there are essentially three ways of addressing this:

1. 使用不同的变量重新构建模型，从而本质上减少了表示等效解决方案的方式
2. 添加对称破坏约束，以减少解决方案的总数，但至少保留每个等价类中的一个.通常，这是通过算术或词典顺序约束来完成的，它们有效地定义了解决方案的规范"表示形式.
3. 尝试系统提供的动态对称破坏技术，例如

1. reformulate the model with different variables such that there are inherently fewer ways of representing equivalent solutions
2. add symmetry-breaking constraints to reduce the total number of solutions but keep at least one of each equivalence class. This is typically done with arithmetic or lexicographic ordering constraints, which effectively define how a "canonical" representation of a solution should look like.
3. try a dynamic symmetry breaking technique that your system provides, such as ldsb. These typically take a description of the symmetry, and try to do something about it (but don't expect wonders).

在您的情况下，我将从点1开始:您当前有变量 A [I，D] = W ，尽管您所有的A插槽都等效.

In your case, I would start with point 1: you currently have variables A[I,D]=W meaning "slot I of type A on day D is filled with worker W" although all your A-slots are equivalent.

您可以改为使用二进制变量 JobA [D，W] = 1 工人W在D天完成了A类工作"，并加上了约束sum(JobA[D,*])#=10以确保您拥有填充了10个插槽.

You could instead have binary variables JobA[D,W]=1 "worker W does a job of type A on day D", together with a constraint sum(JobA[D,*])#=10 to make sure you have 10 slots filled.

我可以想象的另一个模型具有变量 Job [D，W] = T 工人W在D天完成了类型T的工作"(将您的工作类型T编码为1..3)并使用出现次数/3 或

Another model I can imagine is having variables Job[D,W]=T "worker W does job of type T on day D" (encoding your job types T as 1..3) and use occurrences/3 or gcc/2 constraints to enforce your various conditions.

这篇关于Eclipse CLP标记:排除排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！