需要帮助来定义适当的约束条件

Question

我很新来约束编程，并试图找到一些真实的情况来测试它。 我发现一个我认为可能与CP解决。

它在这里： 我有一群孩子，我必须分配给一些活动。 这些孩子填写一个表格，他们按照喜好指定3个选项。 活动有最大数量的参与者，所以，想法是找到一个解决方案，其中的选择是最好的，没有beyondind max。

因此，在第一种方法中，我为[1,2,3]域定义了孩子的变量（选择的数量，活动和孩子在其他地方知道的链接）。然后，我真的不知道如何定义相关的约束，所以我有所有的排列（很长），然后，我必须给每个注释（添加选项的数量来获得最小值）并消除与大集团的结果。

我认为必须有一个很好的方法来使用CP来做到这一点，但我无法弄清楚。

有人可以帮助我吗？

感谢

Answer 1

我不知道我理解你的描述的一切，例如：“所以我把所有的置换（很长）”和“我给了一张字条给每个（添加数字的选择获得最小值）“。也就是说，这是一个简单的编码，我认为这是你问题的一个模型，或者至少是一个初学者。

它是用MiniZinc写的，下面显示了一个6个孩子和4个活动的小例子。完整的模型（包括一些约束的变体）也在这里：http://hakank.org/minizinc/max_activity.mzn

变量的描述： “x”是一个包含每个孩子选定活动的决策变量数组。 “分数”是所选活动的分数（1,2或3取决于选择的活动），“total_score”只是将“分数”数组相加。

include "globals.mzn"; 
int: num_kids; 
array[1..num_kids, 1..3] of int: prefs; 

int: num_activities; 
array[1..num_activities] of int: activity_size; 

% decision variables 
array[1..num_kids] of var 1..num_activities: x; % the selected activity 
array[1..num_kids] of var 1..num_activities: scores; 
var int: total_score = sum(scores); 

solve maximize total_score; 

constraint 
    forall(k in 1..num_kids) (
    % select one of the prefered activities 
    let { 
     var 1..3: p 
    } in 
     x[k] = prefs[k,p] /\ 
     scores[k] = 4-p % score for the selected activity 
    ) 

    /\ % ensure size of the activities 
    global_cardinality_low_up(x, [i | i in 1..num_activities], [0 | i in 1..num_activities], activity_size) 
; 

output [ 
    "x  : ", show(x), "\n", 
    "scores: ", show(scores), "\n", 
    "total_score: ", show(total_score), "\n", 
]; 

% 
% some small fake data 
% 
num_kids = 6; 
num_activities = 4; 

% Activity preferences for each kid 
prefs = array2d(1..num_kids, 1..3, 
    [ 
    1,2,3, 
    4,2,1, 
    2,1,4, 
    4,2,1, 
    3,2,4, 
    4,1,3 
]); 

% max size of activity 
activity_size = [2,2,2,3]; 

这个问题实例的解决方案是：

x  : [1, 4, 2, 4, 3, 4] 
scores: [3, 3, 3, 3, 3, 3] 
total_score: 18 

这是一个独特的解决方案。我们得到了另一个最优的解决方案（total_score = 17），因为活动＃4中可能只有2个孩子（孩子＃6在这里被迫取活动＃1，而不是）

X：[1，4，2，4，3，1] 分数：[3，3,3，3,3，2] total_score：17

有是另外两种可能的第二种选择，即

x  : [1, 4, 2, 2, 3, 4] 
scores: [3, 3, 3, 2, 3, 3] 
total_score: 17 
---------- 
x  : [1, 2, 2, 4, 3, 4] 
scores: [3, 2, 3, 3, 3, 3] 
total_score: 17 

更新：我也做了一个使用相同主体方法的Picat模型：http://hakank.org/picat/max_activity.pi。

更新2：上述模型假定所有的孩子都会得到一些他们喜欢的活动。当这个假设没有得到满足时，人们就会以某种方式解决这个问题，而不是仅仅抛出一个“无法接受”作为答案。一种方法是选择一些其他的 - 不是首选 - 活动的孩子，这将产生一个得分的0。这在这个模型做：http://hakank.org/minizinc/max_activity2.mzn

相比原车型的变化较小：

• 的“得分”的域是0..num_activities
• 我们添加一个脱节“/分数[K] = 0”到forall的环，其选择的活性

由于这是一个最大化问题的得分除非必要，否则不会使用0。

我还添加了一个合理性检查，有足够的活动，为所有的孩子：

constraint 
    assert(sum(activity_size) >= num_kids, "There is not activities enough for all kids.") 
;