需要幫助來定義適當的約束條件

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.") 
;